Problemy, które można rozstrzygać, ale których nie można zweryfikować w czasie wielomianowym

Pracując nad nieco niezwiązanym projektem dla Suresh, ostatnio natknąłem się na pracę wykonaną przez Page i Opper na temat systemów tworzonych przez użytkowników, a część ich pracy krótko omówiła problemy, których nie można zweryfikować w czasie wielomianowym. Nie udało mi się znaleźć wielu informacji o innych problemach, których nie można zweryfikować w czasie wielomianowym lub analizie takiego problemu. Zastanawiałem się, czy ktoś z was wiedział o takich problemach i / lub jak je analizować.

Jak stwierdzono w komentarzach, lepszym sposobem sformułowania tego pytania jest: Jakie problemy są rozstrzygalne, ale poza NP?

Najważniejszą rzeczą do zrealizowania z teoretycznego punktu widzenia jest to, że NP jest w rzeczywistości stosunkowo małą klasą wszystkich rozstrzygalnych języków. To powiedziawszy, wiele interesujących problemów w informatyce leży w NP, więc przyciągają wiele uwagi.

$NP \subsetneq PH \subsetneq PSPACE \subsetneq EXP \subsetneq NEXP$

$R \setminus NP$$NP \subsetneq NEXP$

Oto kilka interesujących konkretnych przykładów problemów w niektórych z tych innych klas:

• Ustalenie, czy gracz ma strategię wygraną w szachy lub w Go (dostosowaną do plansz NXN), kończy EXP.
• MAJ-SAT, problem określania, czy ponad połowa przypisań do zmiennych w formule boolowskiej spełnia tę formułę, dotyczy PSPACE. Jest również kompletny dla mniejszej klasy PP.
• $\Sigma_2^P$

Rozszerzając komentarz Hsien-Chiha Changa, każdy trudny problem związany z NEXP nie może znajdować się w NP, dlatego z definicji nie można go zweryfikować w czasie wielomianowym.

Można użyć niedeterministycznego twierdzenia o hierarchii czasu, aby zobaczyć, że NP jest ściśle zawarty w NEXP. Dlatego możemy być pewni, że biorąc pod uwagę jakikolwiek trudny problem związany z NEXP, nie ma go w NP lub prowadzilibyśmy w sprzeczności.