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

12

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 .

Shlomi Fisch
quelle

Antworten:

27

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 .Af(n)Af(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.Af(n)2f(n)A2f(n)

Es folgt dem:

NP PSPACE

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

Beziehungen zwischen Klassen

Die Erklärung ist einfach: Ein Problem Q NP hat ein polynomielles Längenzertifikat y . Ein Algorithmus, der alle möglichen Zertifikate testet, ist ein Algorithmus, der Q in der Zeit 2nO(1) .

Sein Platzbedarf beträgt:

  • y (Polynom inn )
  • 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, φ ist eine Instanz von 3-CNF in Literalen x1xn mit m Sätzen. Eine Zuweisung f ist eine Funktion f:{x1xn}{0,1} .

Es gilt:

  • Es gibt 2n verschiedene Zuordnungen.
  • Wenn eine Zuweisung f , dauert es O(m) Zeit, um den Wert von φ 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 PSPACE , und da 3-SAT NP-vollständig ist, ist NP PSPACE

LOX
quelle
1
Warum hängen EXPSPACE und EXPTIME zusammen? Ich dachte, Zeit und Raum wären unterschiedliche Ressourcen. Ein Beispiel, das mir in den Sinn kommt, ist das Brechen eines Kryptoschemas, das EXPTIME, aber konstanten Speicherplatz erfordert
WeCanBeFriends,
6
Das intuitive hier ist, wenn Sie Raum verwenden, müssen Sie mindestens f ( n ) Zeit verwenden, und Sie sollten nicht mehr als 2 f ( n ) Zeit verwenden, weil Sie dann die gleichen Zustände wiederholen müssen. Deshalb PSPACE EXPf(n)f(n)2f(n)
lox
Unterscheidet sich f (n) in Ihrem Beispiel von O (n)?
WeCanBeFriends
1
@WeCanBeFriends Exponentielle Zeit kann nicht mit konstantem Speicherplatz verwendet werden: Sie benötigen mindestens den Speicherplatz, der zum Zählen bis zu dieser exponentiellen Zahl (z. B. dem Programmzähler einer Assemblersprache) verwendet wird, die polynomisch ist (logarithmisch im Exponentiellen)
Gigabyte
4
PEXPTIME
9

Ja. Hier ist eine Skizze eines direkten Beweises.

Wenn ein Problem in 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 cp(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)ncp(n)p(n)cp(n) aber das ist Polynom, also ist es OK). Simulieren Sie dann die Operation von M und verwenden Sie imi ten Schritt der Berechnung diei te Ziffer der Zahl, um zu entscheiden, welche nicht deterministische Wahl getroffen werden soll. Wenn zum Beispiel diei 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 00 , 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 c1 . Wir haben jetzt alle möglichen Berechnungspfade simuliert und dies rechtzeitig um cp(n)p(n) mit einem Abstand von etwa 2p(n) . Das ist exponentielle Zeit und Polynomraum, je nach Bedarf.

David Richerby
quelle