NP-harte Probleme, die nicht in NP sondern entscheidbar sind

31

Ich frage mich, ob es ein gutes Beispiel für ein leicht verständliches NP-Hard- Problem gibt, das nicht NP-Complete und nicht unentscheidbar ist.

Zum Beispiel ist das Stopp-Problem NP-Hard, nicht NP-Complete, aber unentscheidbar.

Ich glaube, dass dies bedeutet, dass es ein Problem ist, für das eine Lösung verifiziert werden kann, aber nicht in polynomieller Zeit. (Bitte korrigieren Sie diese Aussage, falls dies nicht der Fall ist.)

man selbst
quelle
Ein kurzer Blick auf den Komplexitätszoo lässt diese Frage fast albern erscheinen - es gibt so viele Klassen zwischen NP und R! Natürlich kennen wir nicht alle Einschlüsse als streng, deshalb gibt es hier etwas Interessantes.
Raphael

Antworten:

33

N E X P N P N E X P N P N E X PNPNEXPNEXPNPNEXPNPNEXP

  • 3-Farbigkeit von Graphen, die durch kurze Schaltkreise beschrieben werden - oder jedes andere NP-vollständige Problem bei Graphen - wobei ein "kurzer Schaltkreis" ein Format zur Darstellung sehr großer Graphen am Eingang ist: anstelle der expliziten Darstellung eines Graphen, z. B.  durch Adjazenzlisten, wir stellen stattdessen eine Schaltung bereit, die eine Funktion berechnet, die die Koeffizienten von a berechnet Adjazenzmatrix.2 n × 2 nf:{0,1}n×{0,1}n{0,1}2n×2n

  • (Nicht-) Äquivalenz zweier regulärer Ausdrücke, bei denen der Kleene-Stern durch Quadrieren ersetzt wird (wobei ein Teilmuster genau zweimal und nicht null oder mehrmals wiederholt wird), und bei der wir uns fragen, ob zwei solcher regulärer Ausdrücke unterschiedliche Mengen von Zeichenfolgen darstellen.

Beachten Sie, dass im letzteren Fall, wenn wir reguläre Ausdrücke verwenden, wie wir es gewohnt sind, einschließlich des Kleene-Sterns, das resultierende Problem -vollständig ist: weil wir die Containments , dies ist immer noch ein entscheidbares Problem, das -hart ist und nicht in .N PN E X PE X P S P A C E N P N PEXPSPACENPNEXPEXPSPACENPNP

Niel de Beaudrap
quelle
7

Haftungsausschluss: Diese Antwort basiert auf der Annahme, dass eine Hypothese ist, an die die meisten Wissenschaftler stark glauben, die wir jedoch noch nicht beweisen müssen. Dies bedeutet, dass diese Probleme möglicherweise in und damit auch in vorliegen.NP NPPSPACENPNPNP

Ich würde sagen, die einfachsten sind True quantified Boolean Formula und Generalized Geography , beide sind -vollständig.PSPACE

TQBF erhält eine quantifizierte Boolesche Formel. Prüfen Sie, ob die Formel wahr ist, dh Formeln in der Form ist falsch, da das Setzen von auf false eine falsche Aussage ergibt.zxyz.[(xy)z]z

Generalized Geography ist ein unterhaltsames Spiel (siehe Wortkette ), bei dem Sie eine Liste von Zeichenfolgen (z. B. Städtenamen) haben und Spieler 1 mit einem Namen beginnt und Spieler 2 mit einem Namen antwortet, der mit dem Buchstaben beginnt, mit dem der vorherige Name endet. Dann ist Spieler 1 an der Reihe, bis jemand feststeckt (es wird empfohlen, dieses Spiel als Trinkspiel zu spielen, bei dem es sich um Bands / Künstler, Filme, Städte, Hauptstädte, berühmte Mathematiker oder was auch immer auf Ihrem Boot schwimmt handelt) muss natürlich trinken). Das formale Problem ist die Frage "Hat Spieler 1 eine Gewinnstrategie?" .

Pål GD
quelle
9
Ich denke nicht wirklich, dass diese Antwort angemessen ist, da es Klassen gibt, von denen wir wissen, dass sie streng über NP liegen und die dienen können. Zumindest sollten Sie Ihre Antwort so überarbeiten, dass Sie anstelle Ihres Postskripts am Ende stattdessen zu Beginn Ihrer Antwort sagen , dass Ihre Antwort von (an Ungleichheit, von der wir überzeugt sind, ist wahrscheinlich wahr). --- Dieser Kommentar ersetzt einen Kommentar, den ich zuvor gelöscht habe. Entschuldigung für den Spam. NPPSPACE
Niel de Beaudrap