2-NEXPTIME-vollständige Probleme

Wir haben ein Problem und haben einen Algorithmus gefunden, der 2-nexptime zu sein scheint.

Ich würde gerne bekannte 2-Nexptime-vollständige Probleme finden, um eine Untergrenze zu finden.

Ich fand in der Literatur hauptsächlich zwei solche Probleme:

ob PCP als Lösung mit einer Größe von weniger als $2^{2^n}$
und das Bodenbearbeitungsproblem für ein Quadrat der Größe $2^{2^n}$

Ich konnte diese Probleme jedoch nicht in meinen verschlüsseln. Daher würde ich gerne andere 2-NEXPTIME-vollständige Probleme kennen, um erstens mehr Intuition in dieser Klasse zu haben und zweitens im besseren Fall eine Untergrenze zu beweisen.

Ich stelle das Problem hier nicht absichtlich zur Verfügung, um einen umfassenden Überblick über 2-NEXPTIME zu erhalten.

Vielen Dank

complexity-classes time-complexity complexity wece
quelle

Enthalten rekursiver Datalog-Programme in Gewerkschaften von konjunktiven Abfragen (Chaudhuri / Vardi 1997). Es sollte auch andere Logik- oder Datenbankprobleme geben, die 2NEXP-vollständig sind, aber keine anderen spezifischen Probleme fallen mir ein.

András Salamon

@ AndrásSalamon Vielen Dank für Ihre Antwort. Ich habe die Referenz, auf die Sie hingewiesen haben, nicht gefunden. Alles, was ich gefunden habe, war ein früherer Artikel der Autoren, in dem festgestellt wurde, dass dieses Problem 2-EXP-vollständig (und nicht 2-NEXP) ist. Vermisse ich etwas?

Wece

Sie haben Recht, ich habe mich falsch an das Ergebnis erinnert: Das Problem ist 2EXP-vollständig.

András Salamon

Ich würde dies immer als N2ExpTime und nicht als 2NExpTime schreiben, da sich "2" und "Exp" beide auf den Wert der oberen Zeitgrenze beziehen, während sich "N" auf das Maschinenmodell bezieht. Es erscheint nicht selbstverständlich, das Maschinenmodell in die Mitte zu stellen.

Mak

Kann mir bitte jemand die Referenz für die 2-NEXPTIME-Vollständigkeit von PCP mit einer Lösung von weniger als 2 ^ 2 ^ n geben?

Corto

Antworten:

Das offensichtliche N2Exp-Problem ist natürlich das Wortakzeptanzproblem für zeitgebundene nichtdeterministische 2exp-Turing-Maschinen. Die Verwendung kann so schwierig / einfach sein wie das Kacheln mit 2exp, da für die Simulation einer solchen Turing-Maschinenberechnung im Wesentlichen auch ein doppelt exponentiell großes Raster definiert werden muss (2exp viele Konfigurationen von Speicherbändern mit einer Länge von jeweils 2exp), das dann gefüllt wird auf nicht deterministische Weise. In der Praxis läuft das Anzeigen von N2Exp-Untergrenzen häufig darauf hinaus, ein solches Gitter zu erstellen (und sicherzustellen, dass es sich nicht um einen Baum oder etwas anderes mit unzureichender Struktur handelt). Das "N" (Nichtdeterminismus) ist oft ein inhärenter Teil des Problems und nicht so schwer zu bekommen, wenn Sie ein ausreichend großes Gitter haben (wenn nicht, würde man vielleicht zuerst für 2exp schießen).

Ein weiteres praktisches N2ExpTime-vollständiges Problem ist das Argumentieren in der Expressive Description Logics (DL). Insbesondere ist der DL , der dem W3C OWL 2 Web Ontology Language- Standard zugrunde liegt, N2ExpTime-complete (Jewgeni Kasakow: RIQ und SROIQ sind härter als SHOIQ. KR 2008: 274-284). Dies ist wahrscheinlich kein Problem, das Sie bei Reduzierungen verwenden möchten, da die Definition der Logik aufgrund ihrer vielen Funktionen etwas unhandlich ist. Der eigentliche Beweis für die Untergrenze von wurde ebenfalls durch Reduktion auf 2-Exp-Kacheln erstellt. Abhängig von Ihrem Problem kann die für angegebene Konstruktion jedoch inspirierend sein, um zu sehen, wie so große Gitter hergestellt werden. $\mathcal{SROIQ}$ $\mathcal{SROIQ}$ $\mathcal{SROIQ}$

Die Kachelung zeigt auch ein anderes allgemeines Muster: N2Exp ist wirklich wie NP, Sie müssen nur einen Weg finden, um noch größere Probleminstanzen sehr effizient zu codieren. Im Prinzip könnten Sie versuchen, jedes NP-Problem zu vergrößern. Der Grund, warum Kacheln schön sind, ist, dass Sie in diesem Fall nur die Größe des Rasters skalieren müssen (was ziemlich einheitlich ist).

Wenn Ihr Problem jedoch möglicherweise nur 2ExpTime-vollständig ist, könnten Sie mit einer exponentiell räumlich begrenzten alternierenden Turing-Maschinensimulation davonkommen . Wenn Sie Probleme beim Erstellen eines 2exp-Rasters haben, aber exponentielle Größen erreichen können, ist dies möglicherweise einen Versuch wert.

mak
quelle