Redukcja wiele-jeden

W teorii obliczalności i teorii złożoności obliczeniowej redukcja wiele-jeden (zwana także redukcją mapowania ) to redukcja , która przekształca przypadki jednego problemu decyzyjnego w inny problem decyzyjny przy użyciu efektywnej funkcji. Gdzie instancja zredukowana do jest w języku, jeśli początkowa instancja była w swoim języku i nie $L_$ w języku $\ Displaystyle$${\ Displaystyle L_ {2}}$ , jeśli początkowa instancja nie była w swoim języku ${\ Displaystyle L_ {1}}$ . ${\ displaystyle L_ {2}$ więc, jeśli możemy zdecydować, czy instancje są w języku, $zdecydować$ , czy są w jego $}$ język przez zastosowanie redukcji i rozwiązania ${\ Displaystyle L_ {2}}$ . Zatem redukcje można wykorzystać do pomiaru względnej trudności obliczeniowej dwóch problemów. Mówi się, że $} styl wyświetlania L_{1}}$ do $Displaystyle$$L_ {2}}$ , jeśli w kategoriach laika jest trudniejszy do rozwiązania niż $Displaystyle L_$ . Oznacza to, że każdy algorytm, który rozwiązuje, może być również użyty jako część (poza tym stosunkowo prostego) programu, który rozwiązuje ${\ displaystyle L_$${\ Displaystyle L_ {1}}$ .

Redukcje wiele-jeden są szczególnym przypadkiem i silniejszą formą redukcji Turinga . W przypadku redukcji typu wiele-jeden wyrocznię (czyli nasze rozwiązanie dla B) można wywołać tylko raz na końcu, a odpowiedzi nie można modyfikować. Oznacza to, że jeśli chcemy pokazać, że problem A można sprowadzić do problemu B, możemy użyć naszego rozwiązania dla B tylko raz w naszym rozwiązaniu dla A, w przeciwieństwie do redukcji Turinga, gdzie możemy użyć naszego rozwiązania dla B tyle razy, ile potrzebne przy rozwiązywaniu A.

Oznacza to, że redukcje typu „wiele jeden” odwzorowują instancje jednego problemu na instancje innego problemu, podczas gdy redukcje Turinga obliczają rozwiązanie jednego problemu, zakładając, że drugi problem jest łatwy do rozwiązania. Redukcja wielu jeden jest bardziej skuteczna przy rozdzielaniu problemów na odrębne klasy złożoności. Jednak zwiększone ograniczenia dotyczące wielu redukcji sprawiają, że trudniej je znaleźć.

Redukcji wiele-jeden po raz pierwszy użył Emil Post w artykule opublikowanym w 1944 r. Później Norman Shapiro użył tej samej koncepcji w 1956 r. Pod nazwą silna redukowalność .

Definicje

Języki formalne

Załóżmy , $i$ i są językami $.$$odpowiednio$ alfabetami _ $_$ _ Redukcja o wiele jeden z do ${\ Displaystyle$$B}$ jest całkowitą obliczalną funkcją $Gamma ^ {*} }$$\$ tę właściwość, że każde słowo ZA $A}$$displaystyle$ wtedy i tylko wtedy, gdy jest w $B}$ .

$displaystyle$$displaystyle$ \ B } i piszemy ZA { $}$ A

${\ Displaystyle A \ równoważnik _ {\ operatorname {m}} B.}$

Jeśli istnieje iniekcyjna funkcja redukcji wiele-jeden, to mówimy, że A jest 1-redukowalne lub jeden-jeden redukowalne do ${\ displaystyle B}$ i piszemy

${\ Displaystyle A \ równoważnik _ {1} B.}$

Podzbiory liczb naturalnych

$\ subseteq \ mathbb {N}}$ zbiory mówimy, że jest wiele-jeden redukowalny do ${\ Displaystyle A,$$B }$ i piszemy ZA ,

${\ Displaystyle A \ równoważnik _ {\ operatorname {m}} B}$

jeśli istnieje całkowita obliczalna funkcja z $Displaystyle$$x \ w A}$ iff ${\ Displaystyle f (x) \ w B$ . Jeśli dodatkowo jest ${\ displaystyle A$ , mówimy, że jest 1-redukowalne do ${$$\ displaystyle B}$ i piszemy ZA

${\ Displaystyle A \ równoważnik _ {1} B.}$

Jeśli dodatkowo jest $z$ , mówimy, że jest rekurencyjnie izomorficzna B $i$$displaystyle B}$ piszemy ^p.324.

${\ Displaystyle A \ równoważnik B}$

Równoważność wiele-jeden i równoważność 1

ZA ${\ Displaystyle A \ równoważnik _ {\ operatorname {m}} B \ \ operatorname {i} \, B \ równoważnik _ {\ operatorname {m}} A$ my powiedzmy $,$ jest odpowiednikiem wiele-jeden lub m-równoważnym B $\ displaystyle B}$ i napisz

${\ Displaystyle A \ równoważnik _ {\ operatorname {m}} B.}$

Jeśli ${\ Displaystyle A \ równoważnik _ {1} B \ \ operatorname {i} \, B \ równoważnik _ {1} A}$$mówimy$ , jest 1-odpowiednik i napisz ${\ displaystyle B}$

${\ Displaystyle A \ równoważnik _ {1} B.}$

Kompletność wiele-jeden (m-zupełność)

Zbiór nazywa się wiele-jeden kompletny lub po prostu m-kompletny , jeśli jest $displaystyle$$zestaw$ rekurencyjnie przeliczalny jest m-redukowalny do $}$${ \$$styl wyświetlania B}$ .

Stopni

${\ Displaystyle \ equiv _ {m}}$ jest relacją równoważności, jej klasy równoważności nazywane są m-stopniami i tworzą poset z kolejnością indukowaną ${\ Displaystyle {\ mathcal {D}} _ {m}}$ przez ${\ Displaystyle \ równoważnik _ {m}}$ . ^{s. 257}

Niektóre właściwości m-stopni, z których niektóre różnią się od analogicznych właściwości stopni Turinga : ^{s. 555--581}

• Istnieje dobrze zdefiniowany operator skoku na m-stopniach.
• 00 Jedynym m-stopniem ze skokiem _m ′ jest _m .
• Istnieje m stopni $nie$ istnieje $Displaystyle \ mathbf {b$ gdzie ${\ Displaystyle \ mathbf {b} '= \ mathbf {a}}$ .
• Każdy policzalny porządek liniowy z najmniejszym elementem jest osadzony w ${\ displaystyle {\ mathcal {D}} _ {m}}$ .
• $izomorficzna$ pierwszego rzędu z teorią arytmetyki drugiego rzędu.

Istnieje charakterystyka jako $poety spełniającej kilka wyraźnych$ jej ideałów , podobna charakterystyka wymknęła się stopniom Turinga. ^{s. 574-575}

${\ Displaystyle \ equiv _ {1}}$ jest relacją równoważności, a jej klasy równoważności (zwane 1-stopniami ) tworzą poset pod ${\ Displaystyle \ leq _ {1}}$ . Twierdzenie o izomorfizmie Myhilla można określić jako „dla wszystkich zbiorów liczb naturalnych $Displaystyle A \ równoważnik$$}$$iff A \ równoważnik _ {1}$ ", co implikuje ${\ displaystyle \ equiv}$$i$ mają klasy równoważności. ^{str. 325}

Redukcje typu „wiele jeden” z ograniczeniami zasobów

$,$$na$ przykład funkcja redukcji jest obliczalna w czasie wielomianowym, w przestrzeni logarytmicznej przez lub lub projekcje polilogarytmiczne, w których każde kolejne pojęcie redukcji jest słabsze niż poprzednie; zobacz redukcję czasu wielomianu i redukcję przestrzeni logarytmicznej, aby uzyskać szczegółowe informacje.

$A$$uwagę$ problemy decyzyjne $\$ algorytm N , który rozwiązuje przypadki , możemy użyć redukcji wielu jeden z $displaystyle$ do $\ displaystyle B}$ { , aby rozwiązać przypadki ${\ displaystyle A}$ w:

• czas potrzebny na N plus czas potrzebny na redukcję
• maksimum miejsca potrzebnego na N i miejsca potrzebnego na redukcję

Mówimy, że klasa C języków (lub podzbiór potęg zbioru liczb naturalnych) jest domknięta redukowalnością do wielu jeden, jeśli nie istnieje żadna redukcja z języka w C do języka poza C . Jeśli klasa jest zamknięta w ramach redukowalności typu wiele-jeden, wówczas można użyć redukcji typu wiele-jeden, aby pokazać, że problem jest w C , redukując do niego problem w C. Redukcje typu wiele-jeden są cenne, ponieważ większość dobrze zbadanych klas złożoności jest zamknięta w pewnym typie redukowalności typu wiele-jeden, w tym P , NP , L , NL , co-NP , PSPACE , EXP i wiele innych. Wiadomo na przykład, że pierwsze cztery wymienione są zamknięte na bardzo słabe pojęcie redukcji polilogarytmicznych projekcji czasowych. Klasy te nie są jednak zamknięte w ramach dowolnych redukcji wiele-jeden.

Nieruchomości

• Relacje redukowalności wiele-jeden i redukowalności 1 są przechodnie i zwrotne , a zatem indukują preorder na zbiorze mocy liczb naturalnych.
• ${\ Displaystyle A \ równoważnik _ {\ operatorname {m}} B}$ wtedy i tylko wtedy, gdy ${\ Displaystyle \ mathbb {N} \ setminus A \ równoważnik _ {\ operatorname {m}} \ mathbb {N} \ setminus B.}$
• Zbiór jest redukowalny do problemu stopu wtedy i tylko wtedy, gdy jest przeliczalny rekurencyjnie . Mówi to, że w odniesieniu do redukowalności typu wiele-jeden, problem zatrzymania jest najbardziej skomplikowanym ze wszystkich rekurencyjnie przeliczalnych problemów. W ten sposób problem zatrzymania jest ponownie kompletny. Pamiętaj, że nie jest to jedyny problem z ponownym uruchomieniem.
• Wyspecjalizowany problem zatrzymania dla pojedynczej maszyny Turinga T (tj. zestawu danych wejściowych, dla których T ostatecznie się zatrzymuje) jest kompletny wiele-jeden, jeśli T jest uniwersalną maszyną Turinga . Emil Post wykazał, że istnieją rekurencyjnie przeliczalne zbiory, które nie są ani rozstrzygalne , ani m-zupełne, a zatem istnieją nieuniwersalne maszyny Turinga, których indywidualne problemy zatrzymania są mimo wszystko nierozstrzygalne .

Redukcje Karpa

wielomianowa w czasie wielomianowym z problemu A do problemu B (z których oba zwykle muszą być problemami decyzyjnymi ) to wielomianowy algorytm przekształcania danych wejściowych do problemu A na dane wejściowe do problemu B , tak że przekształcone problem ma taki sam wynik jak pierwotny problem. Instancję x problemu A można rozwiązać, stosując tę ​​transformację w celu uzyskania instancji y problemu B , dając y jako wejście do algorytmu dla problemu B i zwracanie jego wyniku. Redukcje wielomianowe w czasie wielomianowym mogą być również znane jako transformacje wielomianowe lub redukcje Karpa , nazwane na cześć Richarda Karpa . Redukcja tego typu jest oznaczona przez $p$ ZA $≤ p$ .