NEXP-vollständige Probleme

31

Es gibt Unmengen von NP-vollständigen Problemen und Quellen, die sie sammeln, z. B. das Buch von Garey und Johnson. Es würde mich interessieren, auch eine Liste von NEXP-vollständigen Problemen zu sehen. Gibt es eine zur Verfügung? Da ich davon ausgehe, dass dies nicht der Fall ist, öffne ich diese Frage (soll dies ein Community-Wiki sein? Ich weiß nichts darüber).

Im Idealfall sollte die Liste die verschiedenen "Arten" von NEXP-vollständigen Problemen abdecken, möglicherweise mit einer gewissen Redundanz, um den Überblick zu behalten, ohne sich zu sehr zu wiederholen. Zum Beispiel ist es gut, zwei oder drei verschiedene prägnante Versionen desselben NP-vollständigen Problems als Beispiele zu haben, wenn die prägnanten Codierungen in leicht unterschiedlichen Formen vorliegen. Nicht ein Dutzend. Eine saubere Möglichkeit, die Redundanz hinzuzufügen, besteht darin, Klauseln der Form "Auch NEXP-vollständig, wenn BLAH" hinzuzufügen. Auch Klauseln der Form "Bleibt NEXP-vollständig, wenn der Eingabediagramm höchstens einen BLAH-Grad hat" sind willkommen.

Lassen Sie mich zum Schluss noch eine persönliche Präferenz hinzufügen. Ich interessiere mich vor allem für vollständige Probleme des "algebraischen" Geschmacks, wenn es welche gibt. Zum Beispiel ist mein Lieblingsproblem # P-complete die bleibende Farbe für ihren algebraischen Geschmack. Ich hoffe, die Gleichheit NEXP = MIP kann auch ein nettes algebraisches NEXP-vollständiges Problem liefern, das mir nicht bekannt ist.

Slimton
quelle
2
Community Wiki!
Dave Clarke
Wie macht man daraus ein Community-Wiki?
Slimton
Melden Sie den Beitrag für die Aufmerksamkeit des Moderators und bitten Sie ihn, ihn in den CW-Modus zu versetzen.
Kaveh
5
warum NEXP? dh warum nicht eine andere Klasse?
Suresh Venkat
1
Beachten Sie, dass die Klasse NEXP manchmal auch als NEXPTIME bezeichnet wird. Dies kann bei Verwendung von Suchmaschinen zu zusätzlichen Ergebnissen führen.
Hermann Gruber

Antworten:

26

Für einige NP-vollständige Probleme gibt es eine SUCCINCT-Variante, die NEXP-vollständig ist.

Ein Beispiel ist SUCCINCT HAMILTON PATH:

  • Eine Boolesche Schaltung mit 2 n Eingängen und einem Ausgang repräsentiert einen Graphen auf 2 n Eckpunkten. Um zu bestimmen, ob es eine Kante zwischen den Eckpunkten i und j gibt , codieren Sie i und j jeweils in n Bits und geben Sie ihre Verkettung an die Schaltung weiter: Es gibt eine Kante zwischen diesen Eckpunkten, wenn die Ausgabe der Schaltung wahr ist. Gibt es bei einer solchen Schaltung einen Hamilton-Pfad in der durch die Schaltung dargestellten Grafik?

Ebenso gibt es SUCCINCT 3SAT, SUCCINCT KNAPSACK usw.

Referenz

  • Hana Galperin und Avi Wigderson (1983), "Prägnante Darstellungen von Graphen", Information and Control 56: 3, S. 183–198.
Gareth Rees
quelle
17

Siehe http://arxiv.org/abs/0905.2419 von Gottesman und Irani. Dies ist ein gutes Beispiel. Grundsätzlich sind wir alle an die Vorstellung gewöhnt, dass die Erfüllung von Bedingungen ein NP-vollständiges Problem sein kann (abhängig von der Geometrie usw.). Sie betrachten jedoch eine Situation, in der alle Bedingungen im Voraus angegeben wurden und die einzige, die Ihnen gestattet ist zu variieren ist, wie groß das System ist. Dies stellt sich jedoch als schwierig heraus, wenn Sie das Problem in der Systemgröße codieren. Das heißt, das Problem wird spezifiziert, indem eine Folge von N Bits angegeben wird, wobei die Größe des Systems von 0 bis 2 ^ N-1 angegeben wird. Die Systemgröße ist also exponentiell größer als die Eingabegröße. Sie zeigen, dass dies NEXP-vollständig ist (und dass das Quantenanalog QMA_EXP-vollständig ist).

Matt Hastings
quelle
15

Lassen Sie mich mit dem Kanonischen beginnen:

Gibt es bei einer nicht deterministischen Turing-Maschine und einer binär geschriebenen Ganzzahl n einen Berechnungspfad für M , der die leere Zeichenfolge in höchstens n Schritten akzeptiert ?MnMn

Auch NEXP-vervollständigen, wenn unär geschrieben ist und maximal 2 n Schritte verlangt werden.n2n

Slimton
quelle
15

2

Ein regulärer Ausdruck ist entweder

  • 0
  • 1
  • ef
  • ef
  • e2

Diese Ausdrücke repräsentieren die Mengen

  • L(0)={0}
  • L(1)={1}
  • L(ef)=L(e)L(f)
  • L(ef)={abaL(e),bL(f)}
  • L(e2)=L(ee)

beziehungsweise.

Beachten Sie, dass, wenn wir den Kleene-Stern (null oder mehr Kopien eines Ausdrucks) als vierten Operator zulassen (zusätzlich zu Vereinigung, Verkettung und Quadrierung), das Problem der Erkennung, ob zwei reguläre Ausdrücke verschiedene Sprachen darstellen, EXPSPACE-vollständig wird .

LJ Stockmeyer, AR Meyer, " Wortprobleme, die exponentielle Zeit erfordern ", 5. STOC, 1973.

Sadeq Dousti
quelle
14

SCHÖNFINKEL – BERNAYS SAT

  • Eine Formel in der Logik erster Ordnung gehört zur Klasse der Schönfinkel-Bernays-Formeln, wenn sie in der Form ausgedrückt werden kann x1x2y1y2φ (mit φkeine Quantifizierer oder Funktionssymbole enthalten). Gibt es ein Modell für eine Schönfinkel-Bernays-Formel?

Referenz

Gareth Rees
quelle
Ist die Umkehrung (Unzufriedenheit) von coNEXP vollständig?
Gigabyte
Ich habe immer gedacht, dass eine logische Formel erster Ordnung φ ohne Quantifizierer eine Boolesche Formel ist. Es ist nicht? Aber für eine Boolesche Formel φ wäre es Σ ^ P_2 abgeschlossen sein. Können die Variablen in einer Schönfinkel-Bernay Formel haben andere Werte als wahr und falsch?
BeniBela
@BeniBela: Das sind also Formeln der Logik erster Ordnung φkann Beziehungssymbole enthalten (deren Bedeutung vom Modell festgelegt werden muss). Siehe die Referenz. Wenn das Modell auf zwei Elemente beschränkt ist, haben wir BINARY SCHÖNFINKEL – BERNAYS SAT, das NEXP-vollständig bleibt .
Gareth Rees