Kann jedes NP-Complete-Problem mit höchstens polynomialem Raum gelöst werden (aber mit exponentieller Zeit?)

Ich habe etwas über NPC und seine Beziehung zu PSPACE gelesen und möchte wissen, ob NPC-Probleme mit einem Algorithmus deterministisch gelöst werden können, der den ungünstigsten polynomiellen Platz benötigt, aber möglicherweise exponentielle Zeit benötigt (2 ^ P (n), wobei P polynomiell ist).

Kann man es auch allgemein auf EXPTIME verallgemeinern?

Der Grund dafür ist, dass ich einige Programme geschrieben habe, um entartete Fälle eines NPC-Problems zu lösen, und sie können für harte Instanzen sehr viel RAM verbrauchen, und ich frage mich, ob es einen besseren Weg gibt. Informationen hierzu finden Sie unter https://fc-solve.shlomifish.org/faq.html .

Im Allgemeinen gilt für jeden Algorithmus Folgendes:

1. Angenommen, ist ein Algorithmus, der in Zeit ausgeführt wird. Dann konnte nicht mehr als Platz einnehmen , da das Schreiben von Bits Zeit erfordert .$A$$f(n)$$A$$f(n)$$f(n)$$f(n)$
2. Angenommen, ist ein Algorithmus, der Platz benötigt. Dann in Zeit, kann jeder seiner verschiedenen Staaten besuchen, daher kann nichts gewinnen , indem sie mehr als das Laufen 2 f ( n ) Zeit.$A$$f(n)$$2^{f(n)}$$A$$2^{f(n)}$

Es folgt dem:

$\mathbf{NP}$ $\subseteq \mathbf{PSPACE}$

Die Anweisung ist als Teil der Beziehungen zwischen den Klassen bekannt, wie im folgenden Diagramm dargestellt:

Die Erklärung ist einfach: Ein Problem $Q$ $\in$ $\mathbf{NP}$ hat ein polynomielles Längenzertifikat $y$ . Ein Algorithmus, der alle möglichen Zertifikate testet, ist ein Algorithmus, der $Q$ in der Zeit $\large 2^{n^{O(1)}}$ .

Sein Platzbedarf beträgt:

• $y$ (Polynom in$n$ )
• Speicherplatz zur Verifizierung von $y$ . Da $y$ ein Polynomzertifikat ist, kann es in Polynomzeit verifiziert werden und benötigt daher möglicherweise nicht mehr als Polynomraum.

Da die Summe zweier Polynome auch ein Polynom ist, kann $Q$ mit dem Polynomraum bestimmt werden.

Beispiel:

Angenommen, $\varphi$ ist eine Instanz von 3-CNF in Literalen $x_1 \dots x_n$ mit $m$ Sätzen. Eine Zuweisung $f$ ist eine Funktion $f:\{x_1\dots x_n\} \rightarrow \{0,1\}$ .

Es gilt:

• Es gibt $2^n$ verschiedene Zuordnungen.
• Wenn eine Zuweisung $f$ , dauert es $O(m)$ Zeit, um den Wert von $\varphi$ zu berechnen , daher kann es nicht mehr als $O(m)$ Raum erfordern .

Ein Algorithmus $A$ , der alle möglichen Zuweisungen überprüft, verwendet also den Polynomraum, läuft in exponentieller Zeit und entscheidet über 3-SAT.

Es folgt dem:

3-SAT $\in \mathbf{PSPACE}$ , und da 3-SAT NP-vollständig ist, ist $\mathbf{NP}$ $\subseteq \mathbf{PSPACE}$

Ja. Hier ist eine Skizze eines direkten Beweises.

Wenn ein Problem in $\mathrm{NP}$ , gibt es eine nicht deterministische Turing-Maschine  $M$ , die es entscheidet, und es gibt ein Polynom  $p$ so dass keiner der Berechnungspfade von $M$ für Eingaben der Länge  $n$ mehr als $p(n)$ Schritte benötigt. Das bedeutet, dass ein einzelner Pfad nicht mehr als $p(n)$ Bandzellen verwenden kann, sodass wir einen einzelnen Pfad deterministisch im Polynomraum simulieren können.

Aber wir müssen alle Pfade simulieren . Nun, es gibt eine Konstante  $c$ , die nur von der Übergangsfunktion von $M$ (und nicht von seiner Eingabe) abhängt,  so dass $M$ bei jedem Schritt  höchstens  $c$ deterministische Wahlmöglichkeiten hat. Das bedeutet, dass es für jede Eingabe der Länge n höchstens $c^{p(n)}$ verschiedene Berechnungspfade gibt  . Wir können alle diese simulieren c p ( n ) Wege wie folgt. Schreiben Sie zunächst eine p ( n ) -Stellenzahl in base- c (dies benötigt Platz p)$n$$c^{p(n)}$$p(n)$$c$$p(n)$ aber das ist Polynom, also ist es OK). Simulieren Sie dann die Operation von $M$ und verwenden Sie im$i$ ten Schritt der Berechnung die$i$ te Ziffer der Zahl, um zu entscheiden, welche nicht deterministische Wahl getroffen werden soll. Wenn zum Beispiel die$i$ te Ziffer $6$ und nur vier Auswahlmöglichkeiten zur Verfügung stehen, verlassen Sie diese Simulation und fahren Sie mit der nächsten fort.

Um nun die gesamte Simulation durchzuführen, schreiben wir die Zahl $0\dots 0$ , simulieren den Pfad von  $M$ , erhöhen die Zahl, simulieren den nächsten Pfad und so weiter, bis wir die Zahl erreichen, bei der jede Ziffer $c-1$ . Wir haben jetzt alle möglichen Berechnungspfade simuliert und dies rechtzeitig um $c^{p(n)}p(n)$ mit einem Abstand von etwa $2p(n)$ . Das ist exponentielle Zeit und Polynomraum, je nach Bedarf.