"Natürliche" entscheidbare Probleme, von denen bekannt ist, dass sie nicht in NP sind.

13

Jedes Mal, wenn ich NP-Vollständigkeit unterrichte, fragen die Schüler: "Gibt es Probleme, von denen bekannt ist , dass sie nicht zu NP gehören?"

Wie würden Sie antworten? Normalerweise gebe ich ihnen ein unentscheidbares Problem als Beispiel, aber dies stellt sich oft nicht gut heraus: (a) Wenn ich ihnen das Halteproblem gebe, denken sie, dass es ein dummer Eckfall ist, und (b) wenn ich ihnen diophantische Gleichungen gebe Ich verstehe nicht, warum es nicht in NP ist (Sie können Lösungen in Poly-Time überprüfen ... schließen Sie sie einfach an! Ich kann sie nur schwer von diesem Ansatz abbringen.)

Ich würde ihnen gerne etwas wie QBF als Beispiel geben, aber es gibt keine nachgewiesene Trennung.

Vorschläge?

Fixee
quelle
1
sollte das CW sein? Es ist eine große Liste ...
Suresh Venkat
@Suresh, es kommt auf deine Vorstellung von natürlich an. Es sollte kurz sein, wenn wir uns auf Studierende beschränken, die "natürlich" genug sind.
Mohammad Al-Turkistany
2
Das Go-Spiel ist PSPACE abgeschlossen. Conways Lebensspiel ist unentscheidbar (dh es ist Turing Machine-Äquivalent) ... sind dies die Arten von Beispielen, die Sie wollten?
user834
1
Die Entscheidung , ob eine Bewegung in einem optimal ist schachbrett ist E X P T I M E - C o m p l e t e . nXnEXPTIMEcomplete
Chazisop
2
@chazisop Es ist nicht bekannt, ob N P enthält . EXPTIMENP
Mark Reitblatt

Antworten:

13

Eine Möglichkeit ist ein Problem, das EXPSPACE-vollständig ist. NP ist trivial in PSPACE enthalten, das in EXPSPACE strikt enthalten ist. Ein Problem, das EXPSPACE-vollständig ist ,Σ besteht darin, zu entscheiden, ob ein regulärer Ausdruck, der eine Exponentiation zulässt, nur Σ ∗ ist .

Suresh Venkat
quelle
Was bedeutet Ihre Notation ? L(R)=L(RRR)
Neel Krishnaswami
Es verallgemeinert das Quadrieren (genau zwei Kopien). Beachten Sie, dass der Verschluss von Kleene beliebig viele Kopien enthält
Suresh Venkat
1
Also ist es dasselbe wie ? Oder sind unendlich viele Wiederholungen enthalten? L(R)=nNL(Rn)
Neel Krishnaswami
Ich denke nicht, dass unendliche Wiederholungen enthalten sind.
Suresh Venkat
Danke und Entschuldigung für die schreckliche Pedanterie. Die Verwendung von ist normalerweise im Zusammenhang klar, aber ich hatte keine. :)
Neel Krishnaswami
11

Da Sie natürliche Probleme hervorheben, ist hier ein sehr natürliches vollständiges Problem, das nicht in N P enthalten ist : Quadratische Kacheln Problem: Wenn eine Reihe endlicher Kacheln gegeben ist, kachelt es ein Quadrat der Größe 2 n x 2 n ?NEXPNP2n2n

Beachten Sie, dass , wenn die quadratische Größe x n ( n in unäre codiert ist) , dann wird das Problem N P -komplette.nnnNP

Für die mit quadratischen tiling -completeness, überprüft die Referenz.NEXP

[1] Christos H. Papadimitriou. Rechenkomplexität. Addison-Wesley, Reading, Massachusetts, 1994

Mohammad Al-Turkistany
quelle
Faszinierend. Das Kacheln eines Quadrats der Größe , in dem n unär dargestellt ist, ist also NP-vollständig; und das Kacheln eines 2 n × 2 n Quadrats, wobei n binär dargestellt ist, ist NEXP-vollständig. Ist das die Idee? Ist etwas über die Komplexität des Kachelns eines n × n- Quadrats bekannt, in dem n binär dargestellt wird? Oder haben Sie gemeint, dass n auch für den ersten Satz Ihrer Antwort unär dargestellt wird? n×nn2n×2nnn×nnn
DW
Ja für deine letzte Frage.
Mohammad Al-Turkistany
Das Kacheln von Quadrat ist NEXP-vollständig, wenn n binär dargestellt wird. n×nn
Mohammad Al-Turkistany
10

Es ist bekannt, dass jedes für oder 2 E X P T I M E abgeschlossene Problem nicht in N P ist (gemäß dem Zeithierarchiesatz). Ähnliches gilt für N E X P S P A C E und E X P S P A C ENEXPTIMEEXPTIMENPNEXPSPACEEXPSPACE(nach Raumhierarchie + Simulation). Sie können oft "falsche" Probleme durch Auffüllen bekommen, aber natürliche Probleme, die für diese Klassen abgeschlossen sind, scheinen nicht ganz so häufig zu sein (wahrscheinlich, weil sie so unglaublich schwer sind!), Aber hier sind ein paar:

EXPSPACE:
Äquivalenz regulärer Ausdrücke mit dem Exponentiationsoperator

2-EXPTIME:
Erfüllbarkeit für CTL * (eine zeitliche Logik)
Erfüllbarkeit für ATL *
Entscheidungsproblem für Presburger Arithmetik

Mark Reitblatt
quelle
3
Die Skolem-Arithmetik, die mit Multiplikation, aber nicht Addition arithmetisch ist, ist ebenfalls entscheidbar. Die Tatsache, dass Sie die Theorie erster Ordnung von einem, aber nicht von Addition und Multiplikation bestimmen können, scheint mir eine ziemlich wichtige Tatsache zu sein.
Neel Krishnaswami
4

Durch Zeit-Hierarchie - Theorem , wenn ist eine zeit konstruierbar Funktion und f ( n + 1 ) = O ( g ( n ) ) ist , dann:g(n)f(n+1)=o(g(n))

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

So liegt beispielsweise kein NEXP-vollständiges Problem in NP vor. Zitieren aus Wikipedia :

Eine wichtige Menge von NEXPTIME-vollständigen Problemen betrifft knappe Schaltungen. Prägnante Schaltungen sind einfache Maschinen, mit denen Graphen auf exponentiell engem Raum beschrieben werden. Sie akzeptieren zwei Vertex-Nummern als Eingabe und Ausgabe, unabhängig davon, ob eine Kante zwischen ihnen liegt. Wenn das Lösen eines Problems in einem Graphen in einer natürlichen Darstellung, z. B. einer Adjazenzmatrix, NP-vollständig ist, ist das Lösen desselben Problems in einer prägnanten Schaltungsdarstellung NEXPTIME-vollständig, da die Eingabe exponentiell kleiner ist. Als ein einfaches Beispiel ist das Finden eines Hamilton-Pfades für einen so codierten Graphen NEXPTIME-vollständig.

Siehe auch Abschnitt "Prägnante Probleme" auf Seite 492 von Papadimitrious Buch .

MS Dousti
quelle
2

Ein Kanalsystem ist eine Menge von endlichen Automaten mit Kommunikationskanälen, über die sie Nachrichten senden können. Eine Nachricht ist ein Buchstabe aus einem Alphabet. In einem verlustbehafteten Kanalsystem können Nachrichten verworfen werden: Ein Brief, der über einen Kanal gesendet wird, kann verschwinden. Das Erreichbarkeitsproblem für verlustbehaftete Kanalsysteme ist bestimmbar, aber nicht primitiv rekursiv.

Für ein sanfteres Beispiel ist das Erreichbarkeitsproblem für Vektoradditionssysteme EXPSpace-schwer.

Vijay D
quelle