Czy każdy trudny problem NP jest obliczalny?

Czy wymagane jest, aby problem trudny do przeprowadzenia w NP był obliczalny?

Nie sądzę, ale nie jestem pewien.

Nie, $NP$ -hard problem nie musi być obliczalny. Definicja jest dość kompletna: problem $L$ jest $NP$ trudny, jeśli ten problem mający rozwiązanie wieloczasowe implikuje, że każdy problem w $NP$ ma rozwiązanie wieloczasowe (to znaczy, redukcja do $L$ istnieje dla każdego problemu w $NP$ .).

Trudne do obliczenia problemy stają się wtedy wyjątkowo trudne: załóżmy, że moglibyśmy rozwiązać jeden problem w czasie wielomianowym. Następnie wykorzystujemy dowód, że nie można go obliczyć, aby wywnioskować, że jest on zarówno obliczalny, jak i niemożliwy do obliczenia - sprzeczność. Z tego fałszu, możemy czerpać wszystko, a mianowicie, że istnieje wielomian algorytm czas na cokolwiek $NP$ problemem mamy do czynienia.

Na przykład, rozważmy problemu stopu $H$ . Możemy zredukować dowolny język A do H w następujący sposób, zakładając, że mamy sprawdzian politytime f ( s , c ), który sprawdza, czy $NP$$A$$H$$f(s,c)$$c$ jest certyfikat $s\in A$ :

• Biorąc pod uwagę dane wejściowe $s$
• Konstrukt (ale nie uruchamiaj) Maszyna Turinga $M$ , który bierze wejściowego $x$ próbuje Każdy certyfikat $c$ i zatrzymuje jeśli $c$ jest certyfikat sprawdzenia, czy $s\in A$ .
• Zwraca (to znaczy zwraca true iff M zatrzymuje się na wejściu x )$H(M,x)$$M$$x$

W ten sposób, za pomocą jednego połączenia do algorytmu poli czasu rozwiązywaniu problemu stopu, można rozwiązać każdy problem w czasie wielomianowym.$NP$

Taka redukcja nie jest przydatna, ponieważ mówi tylko, czy „jeśli fałsz, to coś”. Wiemy już, że nie ma algorytmu czasu policy dla problemów nieobliczalnych.

Wydaje się, że w tej społeczności istnieje znaczne zamieszanie w związku z tym pytaniem. Dam szczegółową odpowiedź w nadziei na oczyszczenie wody i wyjaśnienie związku między obliczalnością a twardością NP.

Po pierwsze, uważam, że jasne i wyraźne określenie różnych definicji rozwiąże wiele zamieszania.

ciąg jest skończony ciąg znaków z pewnym ustalonym skończonym alfabetem.

Problem decyzyjny jest zbiorem ciągów. (Ten zestaw jest zwykle nieskończony). Pomyśl o problemie decyzyjnym jako o testowaniu ciągów dla pewnej właściwości: ciągi z właściwością są w zestawie, a ciągi bez właściwości nie.

Załóżmy, że mamy dwa problemy decyzyjne, i B . Powiedzmy jest wielomianem czasie sprowadzić do B , jeśli nie jest pewne wielomian P ( x ) i algorytm jakiś algorytm K tak, że dla wszystkich ciągów s ,$A$$B$$A$$B$$p(x)$$M$$s$

• Jeśli podasz wejściowe s , M zatrzymuje się w mniej niż p ( | s | ) krokach (gdzie | s | jest długością ciągu s ) i wysyła ciąg M ( s ) .$M$$s$$M$$p(|s|)$$|s|$$s$$M(s)$
• jest A tylko wtedy, gdy M ( y ) w B .$s$$A$$M(s)$$B$

Problem decyzja jest NP-trudne , jeżeli dla każdego problemu NP decyzja A , jest wielomian czasie sprowadzić do B .$B$$A$$A$$B$

Problem decyzyjny jest obliczalny, jeśli istnieje algorytm , który dla wszystkich ciągów $M$$s$ ,

• Jeśli podasz z wejściem s , $M$$s$$M$ zatrzyma i wyjdzie albo „tak” albo „nie”.
• Wyjście to „tak”, jeśli jest w A, a „nie” w przeciwnym razie.$s$$A$

Dzięki powyższym definicjom możemy natychmiast wyjaśnić, co moim zdaniem może być głównym zamieszaniem w twoim pytaniu: nic w definicjach problemu decyzyjnego, redukcji lub twardości NP nie wymaga obliczeń problemów decyzyjnych. Definicje mają doskonały sens, gdy myśli się o problemach decyzyjnych jako o dowolnych zestawach ciągów, które mogą być naprawdę bardzo nieprzyjemne.

To pozostawia dwa pytania na stole:

1. Definicje pozostawiają otwartą możliwość, że funkcje niepoliczalne mogą być trudne dla NP. Czy istnieją w rzeczywistości trudne do obliczenia funkcje NP-trudne?
2. Istnieje intuicja, że ​​stwierdzenie, że problem jest NP-trudny, oznacza, że ​​trudno go rozwiązać. Powiedzenie, że nie można go obliczyć, jest jak powiedzenie, że „naprawdę trudno” go rozwiązać. Czy wszystkie trudne do obliczenia problemy są trudne NP?

Odpowiedź na pytanie 1 jest łatwiejsza. Istnieją dwa szczególnie ważne sposoby znalezienia problemów decyzyjnych, które nie są obliczalne, które są trudne dla NP. Pierwszym z nich jest powstrzymanie problem: zatrzymanie problemem, , ma tę właściwość, że każda obliczalna problem decyzyjny jest wielomian czasie sprowadzić do H . Ponieważ problemy NP są obliczalne, każdy problem NP można wielomianowo zredukować do H , więc H jest trudny do NP.$H$$H$$H$$H$

Innym ważnym sposobem na zbudowanie trudnego do obliczenia problemu NP-trudnego jest zaobserwowanie, że możemy połączyć dowolny znany problem trudny dla NP z dowolnym znanym problemem, który nie jest obliczalny. Niech będzie NP-twarde, a B nie będzie obliczalne. Utwórz problem decyzyjny A ⊕ B w następujący sposób: A ⊕ B zawiera te ciągi znaków w postaci „0, po których następuje ciąg w A ” i ciągi w postaci „1, po których następuje ciąg w B ”. A ⊕ B jest trudne dla NP, ponieważ możemy zmienić dowolną redukcję (dowolnego problemu) na A w redukcję na A ⊕ $A$$B$$A \oplus B$$A \oplus B$$A$$B$$A \oplus B$$A$$A \oplus B$: po prostu popraw algorytm, aby wyświetlał dodatkowe „0” na początku łańcucha wyjściowego. nie jest obliczalny, ponieważ obliczenie A ⊕ B wymaga podjęcia decyzji, które ciągi rozpoczynające się od „1” znajdują się w zestawie; jest to niemożliwe, ponieważ B jest niepoliczalny.$A \oplus B$$A \oplus B$$B$

Pytanie 2 jest znacznie trudniejsze, ale w rzeczywistości występują problemy decyzyjne, które nie są trudne do obliczenia dla NP (przy założeniu P NP). Dobra odpowiedź Yuvala wyraźnie konstruuje taki problem decyzyjny. (Dla dowolnych teoretyków obliczeń w pokoju, każdy „Cohen Π 0 $\neq$$\Pi^0_1$ obliczeń -generic” również załatwi sprawę.) Podzielę się, dlaczego intuicja, że ​​„problemy z NP są trudne, problemy niepoliczalne są trudniejsze " jest źle.

Zarówno twardość NP, jak i brak możliwości obliczeń mówią, że problem jest „trudny” w bardzo ogólnym sensie, ale są one bardzo różne i nie powinny być skupiane razem jako ten sam rodzaj zjawiska. Konkretnie, NP-twardość jest „dodatni” własność: NP-trudnym problemem jest ciężko w tym sensie, że, biorąc pod uwagę dostęp do ściągawki arkuszu A , to może rozwiązać twardy klasę problemów$A$$A$ . Z drugiej strony, niemożność obliczenia jest właściwością „negatywną”: problem niemożliwy do obliczenia trudny w tym sensie, że nie można rozwiązać problemu A przy użyciu danej klasy zasobów$A$$A$ .

(Nawiasem mówiąc, „zmuszanie” jest techniką używaną do wytworzenia „Cohen generic”, o którym wspomniałem. Aby być bardzo nieokreślonym, wymuszanie jest ogólnym sposobem tworzenia rzeczy, które są „ogólne”, ponieważ brak dodatnich właściwości i każda ujemna właściwość. Dlatego wymuszanie może bezpośrednio spowodować problem, który nie jest ani trudny do obliczenia, ani trudny do NP).$\Pi^0_1$

Nie. NP-Hard oznacza, że ​​jest równie trudny lub trudniejszy niż najtrudniejsze problemy z NP. Intuicyjnie, ponieważ nie można go obliczyć, będzie to o wiele trudniejsze niż NP.

Wikipedia:

Występują problemy decyzyjne, które są trudne NP, ale nie NP kompletne, na przykład problem zatrzymania.

Wszyscy wiedzą, że nie można tego obliczyć

Dla kompletności udowodnijmy następujące twierdzenie:

Istnieje język, którego nie można obliczyć, który nie jest trudny do wykonania w NP, tylko wtedy, gdy P NP.$\neq$

Jeśli P = NP, to dowolny nietrywialny język (inny niż $\emptyset,\{0,1\}^*$ ) jest NP-trudny (ćwiczenie), a w szczególności każdy niepoliczalny język jest NP-trudny.

Załóżmy teraz, że P NP. Niech T i być pewne wyliczenie wszystkich maszyn Turinga. Wymagany język L zbudujemy etapami. Na każdym etapie będziemy trzymać { 0 , 1 , ? } kolorowanie { 0 , 1 } ∗, które oznaczamy również przez L ; tutaj 0 oznacza, że ​​zdecydowaliśmy, że łańcuch nie jest w L , 1 oznacza, że ​​zdecydowaliśmy, że łańcuch jest w L , a $\neq$$T_i$$L$$\{0,1,?\}$$\{0,1\}^*$$L$$0$$L$$1$$L$$?$oznacza, że ​​jeszcze nie zdecydowaliśmy. Czy wszystkie skończone struny będą kolorowe .$?$

W kroku , myślimy o T i jako maszyny, które albo akceptuje swoje wejście, odrzuca go, czy nigdy nie zatrzymuje. Jeśli T i nie zawsze się zatrzymuje, nic nie robimy. Jeśli T i zawsze zatrzymuje się, to znajdujemy ciąg x taki, że L ( x ) = ? i ustaw L ( x ) : = 0, jeśli T i ( x ) akceptuje i L ( x ) : = 1, jeśli $2i$$T_i$$T_i$$T_i$$x$$L(x) = ?$$L(x) := 0$$T_i(x)$$L(x) := 1$$T_i(x)$ odrzuca.

W etapie , uważamy , T i za maszynę obliczeniową (ewentualnie) funkcję częściowo na jego wejściu. Jeśli T i nie jest całkowite lub jeśli jest całkowite, ale nie działa w czasie wielomianowym, lub jeśli jest całkowite, ale jego zasięg jest ograniczony, nic nie robimy. Jeśli T i jest całkowite, działa w czasie wielomianowym i ma nieskończony zakres, to znajdujemy ciąg x taki, że L ( T i ( x ) ) = ? . Jeśli x ∈ S A T (to znaczy, jeśli $2i+1$$T_i$$T_i$$T_i$$x$$L(T_i(x)) = ?$$x \in \mathrm{SAT}$$x$koduje zadowalającą CNF), a następnie ustawiamy , a w przeciwnym razie ustawiamy L ( x ) : = $L(x) := 0$$L(x) := 1$ .

Po nieskończenie wielu kroków, otrzymujemy kolorowanie { 0 , 1 } $\{0,1,?\}$$\{0,1\}^*$ które uzupełniamy do rzeczywistego języka w dowolny sposób.

Wynikowy język nie jest obliczalny: krok 2 i zapewnia, że T i go nie oblicza. To również nie jest trudne NP, ale tutaj rozumowanie jest nieco bardziej delikatne. Załóżmy, że T i jest obniżenie polytime z So do L . Jeśli zakres T i jest skończony, wówczas możemy przekształcić T i w maszynę politytime decydującą o SAT, wymieniając tabelę prawdy L na zakresie T i . Jest to niemożliwe przy założeniu P ≠ NP. Zatem T i ma nieskończony zakres, ale następnie krok 2 $L$$2i$$T_i$$T_i$$L$$T_i$$T_i$$L$$T_i$$\neq$$T_i$ wyklucza jego bycie redukcja z SAT do L .$2i+1$$L$

Język jest NP-trudne, jeśli dla każdego L ' ∈ N P mamy, że L ' jest wielomian czasie sprowadzić do L . Problem akceptacji niedeterministycznych maszyn Turinga$L$$L' \in \mathrm{NP}$$L'$$L$

jest nierozstrzygalny i trudny do NP. Do rozważenia . O L ' decyduje jakaś niedeterministyczna maszyna Turinga M ' o wielomianowej złożoności czasowej. Wieloczynnikową redukcję czasu f od L ' do A N T M podano przez$L' \in \mathrm{NP}$$L'$$M'$$f$$L'$$A_{\mathsf{NTM}}$

Myślę, że to, co powoduje, że ludzie myślą, że nie ma trudnego do obliczenia problemu z NP-twardością, polega na tym, że nie rozumieją, że twardość NP jest dolną granicą twardości problemu, a nie górną granicą ich twardości, jak P lub NP.

Język L będący NP-trudny oznacza, że ​​jest ponad językiem w NP i to znaczy. Teraz, jeśli to rozumiesz, musisz pokazać, że istnieje arbitralny trudniejszy problem.

$A$$A$$\mathsf{C}^A$$\mathsf{C}^A$$Halt_{\mathsf{C}^A}$$\mathsf{C}^A$ .

$A$$A'$$A < A'$$A<A'<A''<A'''<...$