Probleme, die entscheidbar sind, aber in der Polynomzeit nicht verifiziert werden können

Bei der Arbeit an einem etwas unabhängigen Projekt für Suresh bin ich kürzlich auf einige Arbeiten von Page und Opper über User-Composable-Systeme gestoßen, und in einem Teil ihrer Arbeit wurden kurz Probleme besprochen, die in polynomieller Zeit nicht verifiziert werden können. Ich konnte nicht viele Informationen über andere Probleme finden, die in der Polynomzeit nicht verifiziert werden können, oder eine Analyse eines solchen Problems. Ich habe mich gefragt, ob jemand von Ihnen solche Probleme kennt und / oder wie man sie analysiert.

Wie in den Kommentaren angegeben, ist ein besserer Weg, diese Frage zu formulieren: Welche Probleme sind zu entscheiden, aber außerhalb von NP?

cc.complexity-theory complexity-classes Scott R
quelle

Probleme außerhalb von

N P

$\mathsf{NP}$

Hsien-Chih Chang 張顯張顯

Ja, speziell diejenigen, die nur nicht in polynomialer Zeit verifiziert werden können.

Scott R

Möglicherweise sehen Sie diese

-kompletten Probleme und reduzieren sie. cstheory.stackexchange.com/questions/3297/…

N E X P

$\mathsf{NEXP}$

Hsien-Chih Chang 張顯張顯

Das Nicht-Hamilton-Problem kann nicht in Polynomzeit verifiziert werden, es sei denn, coNP = NP.

Mohammad Al-Turkistany

@turkistany @ Hsien-Chih Chang, warum nicht Ihre Kommentare oben als Antworten posten.

Kaveh

Antworten:

Theoretisch gesehen ist es am wichtigsten, dass NP eine relativ kleine Klasse aller entscheidbaren Sprachen ist. Das heißt, viele der interessanten Probleme in der Informatik liegen im NP, so dass sie viel Aufmerksamkeit erhalten.

Es ist , dass gemutmaßt . $NP \subsetneq PH \subsetneq PSPACE \subsetneq EXP \subsetneq NEXP$

Die Klassen PH, PSPACE und EXP enthalten viele der "interessanten" Probleme in , nach denen Sie in dieser Frage fragen. Bisher hat NEXP die ganze Aufmerksamkeit auf sich gezogen, weil die einzige richtige Einschließung ist, die wir nachweisen können (durch den Satz der nicht deterministischen Zeithierarchie, wie ich oben erwähnt habe). $R \setminus NP$ $NP \subsetneq NEXP$

Hier einige interessante konkrete Beispiele für Probleme in einigen dieser anderen Klassen:

Die Feststellung, ob ein Spieler eine Gewinnstrategie im Schach- oder Go-Modus (angepasst an nxn-Boards) hat, ist EXP-vollständig.
MAJ-SAT, das Problem, zu bestimmen, ob mehr als die Hälfte der Zuweisungen zu den Variablen in einer Booleschen Formel diese Formel erfüllen, ist in PSPACE. Es ist auch komplett für die kleinere Klasse PP.
EXACT-CLIQUE, das Problem der Bestimmung, ob die größte Clique in einem Graphen genau k groß ist, ist in Teil der zweiten Ebene der Polynomhierarchie. $\Sigma_2^P$

Huck Bennett
quelle

Ist die Klasse der rekursiven Probleme aus Neugier der "Standard" für R? Das scheint der Zoo zu signalisieren, aber ich habe R oft genug als Synonym für RP gesehen, das war meine instinktive Lektüre, als ich R \ NP sah ...

Steven Stadnicki

Ich denke, es ist die Standardnotation. Es passt gut zu "RE" und "Co-RE".

Huck Bennett

Sowohl Schach als auch Go sind aufgrund von Wiederholungsregeln normalerweise EXPTIME-vollständig.

Geoffrey Irving

@GeoffreyIrving: Du hast recht, danke. Fest. Ich bin mir nicht sicher, was ich (aus Versehen) gedacht habe, als ich das geschrieben habe, aber es gibt "Unterprobleme" von Go, wie LADDERS, die PSPACE-vollständig sind: link.springer.com/chapter/10.1007%2F3-540 -45579-5_16

Huck Bennett

Wenn Sie ein PSPACE-Orakel zur Hand hätten, könnten Sie wahrscheinlich ziemlich gut spielen. :)

Geoffrey Irving

In Anlehnung an Hsien-Chih Changs Kommentar kann nicht jedes NEXP-schwierige Problem in NP vorliegen, daher kann per Definition nicht in polynomieller Zeit verifiziert werden.

Man könnte den nichtdeterministischen Zeithierarchiesatz verwenden, um zu sehen, dass NP streng in NEXP enthalten ist. Daher können wir sicher sein, dass es sich bei einem NEXP-schwierigen Problem nicht um ein NP handelt oder dass wir in einen Widerspruch verwickelt werden.

Chazisop
quelle

Beachten Sie jedoch, dass Buhrman, Fortnow und Santhanam ein Orakel konstruieren, zu dem NEXP unendlich oft in NP enthalten ist ( dx.doi.org/10.1007/978-3-642-02927-1_18 ). Mit anderen Worten, es gibt ein Orakel, zu dem es für jedes NEXP-Problem L ein Problem L 'in NP gibt, so dass L bei unendlich vielen Eingangslängen gleich L' ist. Obwohl also unendlich viele Instanzen eines nexp-vollständiges Problem nicht in Poly Zeit überprüft werden kann, können wir nicht (relativizably) regieren die Möglichkeit aus , dass unendlich viele andere Instanzen können in Poly Zeit überprüft werden.

Joshua Grochow