Czy każdy trudny problem NP jest obliczalny?

19

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

Nie sądzę, ale nie jestem pewien.

complexity-theory computability np-hard

— Kevin Meier
źródło

15

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 do w następujący sposób, zakładając, że mamy sprawdzian politytime 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 zatrzymuje się na wejściu ) $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.

— jmite
źródło

7

„Definicja jest dość kompletna”, ale nie jest tym, co wynika z tego cytatu w twojej odpowiedzi.

Mam pytanie na ten temat. Mogę sobie wyobrazić funkcję, która rozwiązuje problem zatrzymania największego możliwego zestawu programów przy pewnych odpowiednich ograniczeniach, ale mogę sobie wyobrazić, że ta funkcja wciąż nie jest obliczalna (w tym sensie, że nigdy nie znaleźlibyśmy jej nawet po nieskończonej ilości czasu) . Jednak jeśli w jakiś sposób udało nam się to rozwiązać, nie jest nawet dla mnie jasne, że powinno to rozwiązać wszystkie problemy trudne NP. Więc albo logika w tej odpowiedzi nie jest zgodna (co oznacza nierozstrzygalne! = Nieobliczalne), albo moje rozumowanie jest błędne (prawdopodobnie). Więc jaka jest wada?

— Mehrdad

12

Większość tej odpowiedzi jest nieprawidłowa, w tym twoja definicja NP trudna: problem A jest trudny NP, jeżeli „dla każdego problemu NP B występuje redukcja czasu B do A.” To nie to samo, co „jeśli A jest wielomianem, to P = NP”. (To drugie jest konsekwencją tego pierwszego, ale nie odwrotnie.) W szczególności prawie na pewno istnieją problemy, których nie można obliczyć, a które nie są trudne NP. Nie opracowałem szczegółów, ale problem członkostwa w wystarczająco ogólnym zestawie (w sensie wymuszania) powinien załatwić sprawę. Zestaw zatrzymania jest w szczególności trudny do pokonania przez redukcję.

7

Pomyśl o redukcji czasu wieloczasowego z A do B w ten sposób: jest to program, który działa w czasie wielomianowym, ale ma specjalną zdolność do zapytania, w jednym kroku, o wyrocznię, która odpowiada przypadkom problemu B. Niezależnie od tego, czy istnieje algorytm wieloczasowy dla B, a nawet czy B jest obliczalny, nadal warto zadać następujące pytanie: zakładając, że wyrocznia poprawnie odpowiada na zadane pytania (w jednym kroku), czy dany program uruchomić w czasie wielomianowym i poprawnie rozwiązać przypadki problemu A?

2

@MikeHaskel Twoja analogia z wyrocznią jest dokładna tylko wtedy, gdy po zapytaniu o wyrocznię program musi zatrzymać się z taką samą odpowiedzią jak ta wyrocznia. W przeciwnym razie co-SAT redukuje się do SAT: odpytuj wyrocznię i neguj. W niektórych pojęciach redukcji, np. Redukcji Turinga, byłoby to do przyjęcia, ale w standardowej redukcji czasu wieloczasowego, a nawet w wielu redukcjach, nie jest to możliwe.

— chi

16

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 . Powiedzmy jest wielomianem czasie sprowadzić do , jeśli nie jest pewne wielomian i algorytm jakiś algorytm tak, że dla wszystkich ciągów , $A$ $B$ $A$ $B$ $p(x)$ $M$ $s$

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

jest tylko wtedy, gdy w . $s$ $A$ $M(s)$ $B$

Problem decyzja jest NP-trudne , jeżeli dla każdego problemu NP decyzja , jest wielomian czasie sprowadzić do . $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 , $M$ $s$ $M$ zatrzyma i wyjdzie albo „tak” albo „nie”.

Wyjście to „tak”, jeśli jest w 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:

Definicje pozostawiają otwartą możliwość, że funkcje niepoliczalne mogą być trudne dla NP. Czy istnieją w rzeczywistości trudne do obliczenia funkcje NP-trudne?
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 . Ponieważ problemy NP są obliczalne, każdy problem NP można wielomianowo zredukować do , więc 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 nie będzie obliczalne. Utwórz problem decyzyjny w następujący sposób: zawiera te ciągi znaków w postaci „0, po których następuje ciąg w ” i ciągi w postaci „1, po których następuje ciąg w ”. jest trudne dla NP, ponieważ możemy zmienić dowolną redukcję (dowolnego problemu) na w redukcję na $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 wymaga podjęcia decyzji, które ciągi rozpoczynające się od „1” znajdują się w zestawie; jest to niemożliwe, ponieważ 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 $\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 , 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 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$

— Społeczność
źródło

2

Czy nie potrafisz skonstruować niezdecydowanego języka, który nie jest trudny w NP dzięki przekątnej? Przekątna w stosunku do wszystkich decydentów i wszystkich redukcji czasu antenowego z SAT.

— Yuval Filmus

1

@YuvalFilmus To prawdopodobnie działa, tak. Myślę, że zapisanie szczegółów, dlaczego możliwe jest przekątne w stosunku do redukcji czasu antenowego z SAT, jest podobne w smaku do pokazania, że wymuszanie działa, więc nie pomyślałem o tym w tych kategoriach.

1

@YuvalFilmus Dodałem również wyjaśnienie, że musisz teraz założyć P

NP: zdecydowanie był krok w moim dowodzie, który brzmiał: „weź jakiś problem w NP, ale nie w P.”

\neq

$\neq$

1

@aelguindy Nie jestem pewien, jaka jest najbardziej dostępna metoda, aby to udowodnić. Wspomniałem o technice forsowania , która jest bardzo ogólna i potężna. Nauczyłem się tego od ludzi, a nie od podręczników, więc osobiście nie znam doskonałego odniesienia do wymuszania. Jednak, jak zauważył Yuval, wymuszanie jest prawdopodobnie przesadą: prawdopodobnie działa bardziej bezpośredni argument dotyczący diagonalizacji. Soare „Rekurencyjnie wyliczalne zestawy i stopnie” to podręcznik, który omawia wiele tego rodzaju argumentów, jeśli chcesz się z nim zapoznać. Znowu jednak większość z nich to prawdopodobnie przesada. ...

1

@aelguindy Również, jeśli myślisz o zestawie problemów decyzyjnych jako przestrzeni topologicznej, prawdopodobnie możesz przeforsować twierdzenie Baire'a, aby uzyskać dowód. Twierdzenie to jest ściśle związane z wymuszaniem, ale jest starsze i bardziej bezpośrednie.

11

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ć

— Zniszczalna cytryna
źródło

4

Zauważ, że chociaż niektóre problemy, które nie są obliczalne (takie jak problem zatrzymania), są trudne dla NP, nie oznacza to, że wszystkie problemy nieobliczalne są trudne dla NP. Zobacz moje komentarze do odpowiedzi jmite. Twardość NP jest pozytywną właściwością: mówi, że odpowiedzi na Twój problem mogą pomóc rozwiązać problemy NP. Bycie twardym NP oznacza, że problem jest do pewnego stopnia trudny. Nie wszystkie trudne problemy są trudne NP.

@MikeHaskel: Posiadanie rozwiązania problemu zatrzymania redukuje wszystkie problemy do poziomu trudności P * problemu zatrzymania ..

— Joshua

1

@Joshua: To nie ma sensu. To jest jak fragment non-proof. Co w ogóle oznacza, że problem ma skończoną liczbę bitów w swoim rozwiązaniu i dlaczego według ciebie dotyczy to wszystkich problemów, których nie można obliczyć? Co rozumiesz przez „P * zatrzymuje”? Jaka jest reszta „redukcji przez n-ty kawałek ...”?

— użytkownik2357112 obsługuje Monikę

1

@Joshua: Wygląda na to, że podstawowym problemem jest założenie, że każdy problem odpowiada maszynie Turinga. Nie każdy problem odpowiada maszynie Turinga. Nie problem()możemy wywołać żadnej funkcji.

— użytkownik2357112 obsługuje Monikę

1

Prawdopodobnie powinieneś przenieść to na czat lub coś w tym stylu

— Destructible Lemon

9

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 być pewne wyliczenie wszystkich maszyn Turinga. Wymagany język zbudujemy etapami. Na każdym etapie będziemy trzymać kolorowanie które oznaczamy również przez ; tutaj oznacza, że zdecydowaliśmy, że łańcuch nie jest w , oznacza, że zdecydowaliśmy, że łańcuch jest w , 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 jako maszyny, które albo akceptuje swoje wejście, odrzuca go, czy nigdy nie zatrzymuje. Jeśli nie zawsze się zatrzymuje, nic nie robimy. Jeśli zawsze zatrzymuje się, to znajdujemy ciąg taki, że i ustaw jeśli akceptuje i 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 za maszynę obliczeniową (ewentualnie) funkcję częściowo na jego wejściu. Jeśli 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 jest całkowite, działa w czasie wielomianowym i ma nieskończony zakres, to znajdujemy ciąg taki, że . Jeśli (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) := 0$ $L(x) := 1$ .

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

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

— Yuval Filmus
źródło

3

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

A_{N T M} = {⟨ M, w ⟩ ∣ M is a nondeterministic Turing machine that accepts w}

$A_{\mathsf{NTM}} = \{ \langle M,w \rangle \mid M \text{ is a nondeterministic Turing machine that accepts } w \}$

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

f (x) = ⟨ M, x ⟩

$f(x) = \langle M,x \rangle$

— Hans Hüttel
źródło

3

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'''<...$

— Kaveh
źródło