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.
Antworten:
Für einige NP-vollständige Probleme gibt es eine SUCCINCT-Variante, die NEXP-vollständig ist.
Ein Beispiel ist SUCCINCT HAMILTON PATH:
Ebenso gibt es SUCCINCT 3SAT, SUCCINCT KNAPSACK usw.
Referenz
quelle
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).
quelle
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 ?M n M n
Auch NEXP-vervollständigen, wenn unär geschrieben ist und maximal 2 n Schritte verlangt werden.n 2n
quelle
Ein regulärer Ausdruck ist entweder
Diese Ausdrücke repräsentieren die Mengen
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.
quelle
SCHÖNFINKEL – BERNAYS SAT
Referenz
quelle