„Naturalne” rozstrzygalne problemy, o których wiadomo, że nie występują w NP.


13

Za każdym razem, gdy uczę kompletności NP, uczniowie pytają „czy są jakieś problemy, o których wiadomo, że nie należą do NP?”

Jak byś odpowiedział? Zazwyczaj daję im nierozstrzygalny problem jako przykład, ale często nie wychodzi to dobrze: (a) jeśli daję im problem z zatrzymaniem, myślą, że to jakiś głupi przypadek, i (b) jeśli dam im równania diofantyczne, nie rozumiem, dlaczego nie ma go w NP (możesz sprawdzić rozwiązania w czasie wieloczasowym ... po prostu je podłącz! Mam trudności z dezaktywacją ich w tym podejściu.)

Jako przykład chciałbym podać im coś w rodzaju QBF, ale nie ma udowodnionego podziału.

Propozycje?


1
czy powinno to być CW? to duża lista ...
Suresh Venkat,

@Suresh, To zależy od twojego pojęcia naturalnego. Powinno być krótkie, jeśli ograniczymy się do „naturalnego” wystarczająco dla studentów.
Mohammad Al-Turkistany

2
Gra Go jest ukończona w PSPACE. Gra życia Conwaya jest nierozstrzygalna (tj. Odpowiednik maszyny Turinga) ... czy tego typu przykłady chciałeś?
user834

1
Zdecydowanie, czy ruch jest optymalny na szachownicy jest . E X P T I M E - c o m p l e t enXnEXPTIMEcomplete
chazisop

2
@chazisop nie wiadomo, czy poprawnie zawiera . N PEXPTIMENP
Mark Reitblatt,

Odpowiedzi:


13

Jedną z możliwości jest problem z funkcją EXPSPACE. NP jest trywialnie w PSPACE, który jest ściśle zawarty w EXPSPACE. Jednym z problemów zakończonych EXPSPACE jest decyzja, czy wyrażenie regularne, które umożliwia potęgowanie, to całeΣ .


Co oznacza twoja notacja ? L(R)=L(RRR)
Neel Krishnaswami,

Uogólnia kwadratowanie (pobranie dokładnie dwóch kopii). Należy pamiętać, że zamknięcie Kleene ma dowolnie wiele kopii
Suresh Venkat

1
Czyli to samo co ? A może nieskończone powtórzenia? L(R)=nNL(Rn)
Neel Krishnaswami,

Nie sądzę, że nieskończone powtórzenia są uwzględnione.
Suresh Venkat

Dzięki i przepraszam za okropną pedanterię. Użycie jest zwykle jasne w kontekście, ale nie miałem żadnego. :)
Neel Krishnaswami,

11

Skoro nacisk na naturalne problemy, oto bardzo naturalny problem z który nie występuje w : Problem z kwadratowymi kafelkami: Biorąc pod uwagę zestaw skończonych kafelków, czy kafelek ma kwadrat o rozmiarze x ?N P 2 n 2 nNEXPNP2n2n

Zauważ, że gdy rozmiar kwadratu wynosi x ( jest zakodowany jako unarny), problem staje się .nnnNP

Aby kwadratowych kafelków, sprawdź odnośnik.NEXP

[1] Christos H. Papadimitriou. Złożoność obliczeniowa. Addison-Wesley, Reading, Massachusetts, 1994


Fascynujący. Zatem ułożenie kwadratu o rozmiarze , gdzie jest reprezentowane w jednostkowej, jest NP-zupełne; i kafelkowanie kwadratu , gdzie jest reprezentowane w postaci binarnej, jest NEXP-complete. Czy to jest pomysł? Czy jest coś znanego na temat złożoności układania kwadratu, gdzie jest reprezentowane w postaci binarnej? A może miałeś na myśli, że jest reprezentowane w jedności nawet przez pierwsze zdanie twojej odpowiedzi? n×nn2n×2nnn×nnn
DW

Tak na twoje ostatnie pytanie.
Mohammad Al-Turkistany

Układanie kwadratu kończy NEXP, gdy jest reprezentowane w postaci binarnej. n×nn
Mohammad Al-Turkistany

10

Jakikolwiek problem ukończony dla lub 2 jest znany z tego, że nie występuje w (według twierdzenia o hierarchii czasu). Podobnie dlaNEXPTIMEEXPTIMENPNEXPSPACEEXPSPACE

EXPSPACE:
Równoważność wyrażeń regularnych z operatorem potęgowania

2-WYŁĄCZENIE:
Zadowolenie dla CTL * (logika czasowa)
Zadowolenie dla ATL *
Problem decyzyjny dla arytmetyki Presburger


3
Rozróżnia się również arytmetykę Skolema, która jest arytmetyką z mnożeniem, ale bez dodawania. Fakt, że możesz zdecydować o teorii pierwszego rzędu jednego, ale nie zarówno dodawania, jak i mnożenia, wydaje mi się dość ważnym faktem.
Neel Krishnaswami,


4

g(n)f(n+1)=o(g(n))

NTIME(f(n))NTIME(g(n))

Na przykład żadnego problemu pełnego NEXP nie ma w NP. Cytowanie z Wikipedii :

Ważny zestaw problemów uzupełniających NEXPTIME dotyczy zwięzłych obwodów. Zwięzłe obwody to proste maszyny do opisywania wykresów w wykładniczo mniejszej przestrzeni. Akceptują dwie liczby wierzchołków jako dane wejściowe i wyjściowe, niezależnie od tego, czy istnieje między nimi krawędź. Jeśli rozwiązanie problemu na wykresie w naturalnej reprezentacji, takiej jak macierz przylegania, jest NP-zupełne, wówczas rozwiązanie tego samego problemu na zwięzłej reprezentacji obwodu jest NEXPTIME-complete, ponieważ dane wejściowe są wykładniczo mniejsze. Jednym prostym przykładem jest znalezienie ścieżki Hamiltona dla tak zakodowanego wykresu NEXPTIME-complete.

Zobacz także sekcję „Zwięzłe problemy” na stronie 492 książki Papadimitriou .



2

System kanałów to zestaw skończonych automatów z kanałami komunikacyjnymi, za pomocą których mogą wysyłać wiadomości. Wiadomość to litera alfabetu. W systemie z kanałami stratnymi wiadomości mogą być usuwane: list przesłany przez kanał może zniknąć. Problem osiągalności systemów z kanałami stratnymi jest rozstrzygalny, ale nieprymitywny rekurencyjny.

Dla delikatniejszego przykładu problem z osiągalnością systemów dodawania wektorów jest trudny w EXPSpace.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.