Redukcja czasu zliczania wielomianowego

W teorii złożoności obliczeniowej problemów zliczania , redukcja zliczania w czasie wielomianowym jest rodzajem redukcji (transformacji z jednego problemu do drugiego) używanej do zdefiniowania pojęcia kompletności dla klasy złożoności ♯P . Redukcje te można również nazwać wielomianowymi redukcjami liczącymi wiele jeden lub słabo oszczędnymi redukcjami ; są analogiczne do redukcji wiele-jeden dla problemów decyzyjnych i uogólniają oszczędne redukcje .

Definicja

$w$$w czasie wielomianowym jest zwykle używana$ przekształcania przypadków znanego trudnego problemu przypadki innego problemu , który ma zostać udowodniony. Składa się z dwóch funkcji $i$ , $z$ obie muszą być obliczalne w wielomianowym . Funkcja przekształca dane wejściowe dla $\ displaystyle X}$$w$ dane wejściowe dla $\$$displaystyle Y}$$X}$ a funkcja przekształca dane wyjściowe dla danych wyjściowych dla $displaystyle$ .

Te dwie funkcje muszą zachować poprawność danych wyjściowych. To znaczy, załóżmy, że przekształca się dane wejściowe dla problemu $}$$X$ na dane wejściowe $\ Displaystyle y = f (x)}$ dla problemu ${\ displaystyle Y} , a następnie$$displaystyle$ się , aby uzyskać wynik $z}$ . Musi być tak, że przekształcone wyjście ${\ displaystyle g (z)}$ jest poprawnym wyjściem dla oryginalnego wejścia ${\ displaystyle x}$ . Oznacza to, że jeśli relacje wejście-wyjście $\ displaystyle Y}$ i ${$ są wyrażone jako funkcje, to ich skład funkcji musi być zgodny z tożsamością ${\ Displaystyle X = g \ cyrk Y\circ f}$ . Alternatywnie, wyrażony w kategoriach algorytmów , jeden możliwy algorytm do rozwiązania $X}$$displaystyle$ byłoby zastosować , aby przekształcić $instancję$ w instancję , rozwiązać tę a następnie zastosować, aby przekształcić wyjście ${\ displaystyle Y}$${\ displaystyle g}$ na poprawną odpowiedź dla ${\ displaystyle X}$ .

Stosunek do innych rodzajów redukcji

W szczególnym przypadku oszczędna redukcja to transformacja w czasie wielomianowym $wejściowych$ do problemów, która zachowuje dokładne wartości wyników. Taka redukcja może być postrzegana jako redukcja zliczania w czasie wielomianowym, przy użyciu funkcji tożsamości jako funkcji ${\ displaystyle g}$ .

Zastosowania w teorii złożoności

Problem funkcjonalny (określony przez jego wejścia i pożądane wyjścia) należy do klasy złożoności ♯ P , jeśli istnieje niedeterministyczna maszyna Turinga działająca w czasie wielomianowym, dla której wyjściem problemu jest liczba akceptujących ścieżek Turinga maszyna. Intuicyjnie, takie problemy liczą liczbę rozwiązań problemów w klasie złożoności NP . Mówi się, że problem funkcjonalny $w$ ♯ P-trudny, jeśli istnieje redukcja liczenia czasu wielomianowego z każdego problemu ♯ P do ${\ displaystyle X}$${\ displaystyle Y}$ . Jeśli dodatkowo sam należy do ♯P, to $.$ się $,$ że jest ♯P- (Czasami, jak w oryginalnym artykule Valianta dowodzącym kompletności permanentnej macierzy 0–1 , zamiast tego do zdefiniowania ♯ P-zupełności używa się słabszego pojęcia redukcji, redukcji Turinga ).

Zwykłą metodą udowodnienia, że ​​problem w ${\ displaystyle Y}$ jest ♯P-zupełny, jest rozpoczęcie od pojedynczego znanego problemu ♯P-zupełnego $znalezienie$ redukcji liczenia w czasie wielomianu z ${\ Displaystyle X}$ do ${\ Displaystyle Y}$ . Jeśli ta redukcja istnieje, to istnieje redukcja z $displaystyle$ innego problemu w , uzyskana przez złożenie redukcji z innego problemu do $X}$ z redukcją z ${\ displaystyle X}$ do ${\ displaystyle Y}$ .