"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?

cc.complexity-theory complexity-classes teaching 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

.

n X n

$n X n$

E X P T I M E - c o m p l e t e

$EXPTIME-complete$

Chazisop

2

@chazisop Es ist nicht bekannt, ob

enthält .

E X P T I M E

$EXPTIME$

N P

$NP$

Mark Reitblatt

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 , $\Sigma^*$ besteht darin, zu entscheiden, ob ein regulärer Ausdruck, der eine Exponentiation zulässt, nur .

Suresh Venkat
quelle

Was bedeutet Ihre Notation

?

L (R ↑) = L (R \cdot R \dots R)

$L(R\uparrow) = L(R\cdot R\ldots R)$

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 ↑) = ⋃_{n \in N} L (R^{n})

$L(R\uparrow) = \bigcup_{n \in \mathbb{N}} L(R^n)$

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. :)

\dots

$\ldots$

Neel Krishnaswami

11

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

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

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

unär dargestellt ist, ist also NP-vollständig; und das Kacheln eines

Quadrats, wobei

binär dargestellt ist, ist NEXP-vollständig. Ist das die Idee? Ist etwas über die Komplexität des Kachelns eines

Quadrats bekannt, in dem

binär dargestellt wird? Oder haben Sie gemeint, dass

auch für den ersten Satz Ihrer Antwort unär dargestellt wird?

n \times n

$n\times n$

n

$n$

2^{n} \times 2^{n}

$2^n\times 2^n$

n

$n$

n \times n

$n\times n$

n

$n$

n

$n$

DW

Ja für deine letzte Frage.

Mohammad Al-Turkistany

Das Kacheln von

Quadrat ist NEXP-vollständig, wenn

binär dargestellt wird.

n \times n

$n \times n$

n

$n$

Mohammad Al-Turkistany

10

ist bekannt, dass jedes für oder 2 abgeschlossene Problem nicht in (gemäß dem Zeithierarchiesatz). Ähnliches gilt für und $NEXPTIME$ $EXPTIME$ $NP$ $NEXPSPACE$ $EXPSPACE$ (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

5

Ein einfaches Beispiel ist die Tetrationsfunktion , die nicht einmal in ist ELEMENTARY enthalten ist . Sie könnten eine Entscheidungsversion davon verwenden.

Aaron Sterling
quelle

4

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

. $\operatorname{NTIME}(f(n)) \subsetneq \operatorname{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

Verwandte: cstheory.stackexchange.com/questions/3297/...

arnab

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

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

Antworten: