NP-Trudne problemy, których nie ma w NP, ale są rozstrzygalne

31

Zastanawiam się, czy istnieje dobry przykład łatwego do zrozumienia problemu NP-Hard, który nie jest NP-Complete i nie jest nierozstrzygalny?

Na przykład problem zatrzymania jest NP-trudny, a nie NP-kompletny, ale jest nierozstrzygalny.

Uważam, że oznacza to, że problem można zweryfikować, ale nie w czasie wielomianowym. (Proszę poprawić to oświadczenie, jeśli tak nie jest).

się
źródło
Szybkie spojrzenie na złożoność zoo sprawia, że ​​to pytanie wydaje się niemal głupie - jest tak wiele klas między NP i R! Oczywiście nie wiemy, że wszystkie inkluzje są ścisłe, więc jest tu coś interesującego.
Raphael

Odpowiedzi:

33

Według niedeterministycznej wersji twierdzenia o hierarchii czasowej mamy NPNEXP , gdzie NEXP jest klasą problemów możliwych do rozwiązania w niedeterministycznym czasie wykładniczym. Dlatego wystarczy rozważyć każdy problem, który to NP -hard and in NEXP , ale nie w NP . Na przykład, możemy rozważyć każdy problem NEXP , taki jak

  • 3-kolorowalność wykresów opisanych zwięzłymi obwodami - lub innym problemem NP-zupełnym na wykresach - gdzie „zwięzły obwód” jest formatem reprezentującym bardzo duże wykresy na wejściu: zamiast wyraźnej reprezentacji wykresu, np.  Listami przyległości, zamiast tego udostępniamy obwód obliczający jakąś funkcję f:{0,1}n×{0,1}n{0,1} która oblicza współczynniki 2n×2n macierz przylegania.

  • (Nie-) równoważność dwóch wyrażeń regularnych, w których gwiazdę Kleene zastępuje się kwadratem (powtarzanie pod-wzoru dokładnie dwa razy, a nie zero lub więcej razy), i gdzie pytamy, czy dwa takie wyrażenia regularne reprezentują różne zestawy ciągów.

Zauważ, że w tym drugim przypadku, jeśli weźmiemy pod uwagę wyrażenia regularne, takie jak gwiazda Kleene, wynikającym z tego problemem jest : ponieważ mamy , to wciąż jest rozstrzygalny problem, którym jest -trwały, a nie .EXPSPACENPNEXPEXPSPACENPNP

Niel de Beaudrap
źródło
7

Zastrzeżenie: Ta odpowiedź opiera się na założeniu, że , hipoteza, w którą większość naukowców mocno wierzy, ale musimy ją jeszcze udowodnić. Oznacza to, że istnieje możliwość, że problemy te znajdują się w a zatem także -complete.PSPACENPNPNP

Powiedziałbym, że najprostsze z nich to prawdziwie skwantyfikowana formuła logiczna i uogólniona geografia , oba -kompletne.PSPACE

TQBF otrzymuje skwantyfikowaną formułę logiczną, sprawdź , czy formuła jest prawdziwa, tj. Formuły w formularzu jest fałszem, ponieważ ustawienie na false daje fałszywe wyrażenie.xyz.[(xy)z]z

Geografia uogólniona to fajna gra (patrz łańcuch słów ), w której masz listę ciągów znaków (np. Nazwy miast), a Gracz 1 zaczyna się od wypowiedzenia imienia, a Gracz 2 odpowiada imieniem rozpoczynającym się na literę, na której poprzednia nazwa się kończyła. Potem jest kolej Gracza 1., aż ktoś utknie (ta gra jest zalecana do grania w gry alkoholowe, w których obiektami są zespoły / artyści, filmy, miasta, stolice, sławni matematycy lub cokolwiek płynie łodzią. Ten, który nie może odpowiedzieć w rozsądnym czasie) oczywiście trzeba pić). Problem formalny jest sformułowany jako pytanie „czy Gracz 1 ma strategię wygrywającą” .

Pål GD
źródło
9
Nie sądzę, aby ta odpowiedź była odpowiednia, ponieważ istnieją klasy, które, jak wiemy, są ściśle nad NP, które mogą służyć. Przynajmniej powinieneś skorygować swoją odpowiedź, aby zamiast postscriptu na końcu możesz zamiast tego powiedzieć na początku swojej odpowiedzi, że twoja odpowiedź zależy od (an nierówność, którą jesteśmy przekonani, jest prawdopodobnie prawdą). --- Ten komentarz zastępuje komentarz, który wcześniej usunąłem; przepraszam za spam. NPPSPACE
Niel de Beaudrap,