Optimale NP-Löser

Fix ein NP-vollständiges Suchproblem zB die Suchform von SAT. Die Levinsuche liefert einen Algorithmus zum Lösen von der in gewissem Sinne optimal ist. Im Einzelnen lautet der Algorithmus "Führe alle möglichen Programme in Verzahnung mit der Eingabe , sobald die Antwort zurückgibt prüft, ob sie korrekt ist". Optimal in dem Sinne, dass bei einem Programm , das mit der Zeitkomplexität löst , die Zeitkomplexität von erfüllt ist L X P x P y P X t P ( n ) t L ( n ) $X \subset \lbrace 0,1 \rbrace^* \times \lbrace 0,1 \rbrace^*$$L$$X$$P$$x$$P$$y$$P$$X$$t_P(n)$$t_L(n)$$L$

Dabei ist ein festes Polynom, das vom genauen Berechnungsmodell abhängt$p$

$L$ Optimalität kann etwas stärker formuliert werden. Für jede und eines Programms, das mit dem Versprechen in der Zeit , ist die Zeitkomplexität von auf Eingaben in befriedigt Q X M t M Q ( n ) t M L ( n ) L $M \subset \lbrace 0,1 \rbrace^*$$Q$$X$$M$$t^M_Q(n)$$t_L^M(n)$$L$$M$

Dabei ist ein festes Polynom. Der entscheidende Unterschied ist, dass zB ein Polynom sein kann, auch wennt M Q ( n ) P ≠ N $q$$t^M_Q(n)$$P \neq NP$

Die offensichtliche "Schwäche" von ist der große Faktor in dieser Schranke. Es ist leicht zu erkennen, dass bei einem Algorithmus, der eine Schranke der gleichen Form erfüllt, durch ein Polynom indann ist . Dies liegt daran, dass wir als ein Programm betrachten können, das eine bestimmte Instanz von löst, indem wir die Antwort hart codieren. Ebenso kann, wenn durch eine subexponentielle Funktion vondann wird die exponentielle Zeithypothese verletzt. Die Antwort auf die folgende Frage ist jedoch (für mich) weniger offensichtlich:2 | Q | 2 | Q | | Q | P = N P Q X 2 | Q | | Q $L$$2^{|Q|}$$2^{|Q|}$$|Q|$$P = NP$$Q$$X$$2^{|Q|}$$|Q|$

Unter der Annahme der Exponentialzeithypothese und anderer bekannter Vermutungen (z. B. Nichtentartung der Polynomhierarchie, Existenz von Einwegfunktionen) gibt es bei Bedarf einen Algorithmus. löst st für jede und ein Programm, das mit dem Versprechen in der Zeit , die auf Eingaben in beschränkte Zeitkomplexität von erfülltX M ≤ { 0 , 1 } ≤ Q X M t M Q ( n ) t M A ( n ) A $A$$X$$M \subset \lbrace 0,1 \rbrace^*$$Q$$X$$M$$t^M_Q(n)$$t_A^M(n)$$A$$M$

$$t_A^M(n) < f(|Q|)q(n, t^M_Q(n)) + g(|Q|)$$

wo ist Polynom, ist subexponentiell und ist willkürlich$q$$f$$g$

Wenn die Antwort positiv ist, kann ein Polynom sein? Was ist die Wachstumsrate von (unter ETH eindeutig mindestens exponentiell)? Wenn die Antwort negativ ist, kann Polynom existieren, wenn ETH falsch ist, aber ?$f$$g$$f$$P \neq NP$

Betrachten Sie den folgenden Algorithmus (eine Variante von Levins Algorithmus):

Führen Sie die ersten Algorithmen parallel aus. Führen Sie außerdem parallel einen Brute-Force-Algorithmus aus, der nacheinander alle möglichen Lösungen ausprobiert. (Führen Sie alle Algorithmen mit der gleichen Geschwindigkeit aus.)$n$

Stoppen Sie, wenn einer der Algorithmen eine Lösung findet.

Betrachten Sie zwei Fälle (bei einer Eingabe der Länge ):$x$$n$

• ist einer der ersten n Algorithmen. Danndie Laufzeit ist O ( n ⋅ t M Q ( n ) ) ⋅ p o l y ( n ) .$Q$$n$$O(n \cdot t^M_Q(n)) \cdot \mathrm{poly}(n)$

• ist nicht einer der ersten n Algorithmen (also n < 2 | Q | ). Dann ist die Laufzeit durch die Laufzeit des Brute-Force-Algorithmus begrenzt. Wir haben, dass die Laufzeit 2 n O ( 1 ) = 2 2 O ( | Q | ) ist .$Q$$n$$n < 2^{|Q|}$$2^{n^{O(1)}} = 2^{2^{O(|Q|)}}$

Wir haben

(Hier ist Polynom und g ( n ) ist doppelt exponentiell in n ; wir können die Abhängigkeit von g ( n ) von n verbessern, indem wir die Abhängigkeit von f ( n ) von n verschlechtern .)$f(n)$$g(n)$$n$$g(n)$$n$$f(n)$$n$