Entscheidungsproblem derart, dass jeder Algorithmus einen exponentiell schnelleren Algorithmus zulässt

In Hromkovičs Algorithmics for Hard Problems (2. Auflage) gibt es diesen Satz (2.3.3.3, Seite 117):

Es gibt ein (entscheidbares) Entscheidungsproblem so dass es für jeden Algorithmus , der löst, einen anderen Algorithmus , der auch löst und zusätzlich erfüllt $P$ $A$ $P$ $A'$ $P$
$\qquad \forall^\infty n \in \mathbb{N}. \mathrm{Time}_{A'}(n) = \log_2 \mathrm{Time}_A(n)$

$\mathrm{Time}_A(n)$ ist die Worst-Case-Laufzeit von für Eingaben der Größe und bedeutet "für alle, aber nur für endlich viele". $A$ $n$ $\forall^\infty$

Ein Beweis wird nicht erbracht, und wir haben keine Ahnung, wie wir das anstellen sollen. es ist eigentlich ziemlich kontraintuitiv. Wie kann der Satz bewiesen werden?

complexity-theory Raphael
quelle

Für den Titel vielleicht so etwas wie: "Gibt es ein Entscheidungsproblem, für das ein Lösungsalgorithmus verbessert werden kann?" Das heißt, es ist nur ein Schuss in die Dunkelheit, aber könnte es nicht der Fall sein, dass es ein entarteter Fall für ein triviales Entscheidungsproblem ist? Irgendwie bedeutet es, wenn Sie die Gleichstellung umkehren, dass es immer möglich ist, ein Problem auf eine "schlimmste" Weise zu lösen (indem Sie unnötige Schritte ausführen). Aber das ist nur eine Vermutung.

Charles

Antworten:

Es scheint ein einfacher Fall von Blums Speedup-Theorem zu sein :

Eine Blum Komplexität Maßnahme gegeben und eine Gesamt berechenbare Funktion mit zwei Parametern, dann gibt es insgesamt berechenbares Prädikat (a Boolean berechenbare Funktion geschätzt) , so dass für jedes Programm für , ein Programm existiert für so dass für fast alle $(\varphi, \Phi)$ $f$ $g$ $i$ $g$ $j$ $g$ $x$
$f (x, Φ_{j} (x)) \leq Φ_{i} (x)$ $f(x,\Phi_j(x)) \leq \Phi_i(x)$

Sei das Komplexitätsmaß das Zeitkomplexitätsmaß (dh ist die Zeitkomplexität der Turingmaschine mit dem Code ) und sei . $\Phi_e(x)$ $e$ $f(x,y) = 2^y$

Kaveh
quelle

+1: Hier ist ein Link zum Originalartikel: logic.cse.unt.edu/tarau/teaching/SoftEng/OLD/papersToDiscuss/… .

Aryabhata