Effizienter universeller Problemlöser?

Definieren Sie ein "Problem" als Algorithmus $A$ , der eine natürliche Zahl akzeptiert und 0 oder 1 zurückgibt, was für mindestens ein . Jedes solche wird als "Lösung" für$1$$n \in \mathbb{N}$$n$$A$

Definieren Sie einen „universellen Problemlöser“ ein Algorithmus sein Annahme ein Problem und die Rückkehr eines seiner Lösungen. Zum Beispiel kann arbeiten, indem es alle natürlichen Zahlen durchläuft und ihre Eingabe für sie ausführt, bis Ergebnisse vorliegen (es muss nur bei einer gültigen Eingabe angehalten werden).$U$$U$$1$

Ich möchte Leistungsgrenzen für universelle Problemlöser ausloten

Wenn ein universeller Problemlöser und ein Problem ist, bezeichne die Zeit, die , um eine Ausgabe zu erzeugen, nachdem die Eingabe akzeptiert wurde$U$$A$$t(U, A)$$U$$A$

Ein universeller Problemlöser wird "effizient" genannt, wenn wir für jeden universellen Problemlöser haben$U$$V$

Hier hängt von , aber nicht von$t_V$$V$$A$

Gibt es effiziente universelle Problemlöser?

EDIT: Ich erkannte, dass es möglich ist, die Definitionen von "Problem" und "Universal Problem Solver" in etwas etwas Eleganteres und im Wesentlichen Äquivalentes zu ändern. Ein "Problem" ist ein Algorithmus ohne Eingabe, der 0 oder 1 zurückgibt (was anhält). Ein "universeller Problemlöser" ist ein Algorithmus, der ein Problem annimmt und dessen Ergebnis zurückgibt. Es ist mehr oder weniger eine universelle Turingmaschine

Alte Definition kann auf neue Definition reduziert werden, da wir , wenn ein Problem im alten Sinne ist, ein Problem im neuen Sinne konstruieren können, das nur den trivialen universellen Problemlöser des alten Sinns auf anwendet (den im obigen Text beschriebenen Löser) )$A$$B$$A$

Neue Definition kann auf alte Definition reduziert werden, da gegeben im neuen Sinne ein Problem, können wir konstruieren ein Problem im alten Sinne , die gerade berechnet und vergleicht den Eingang zu dem Ergebnis ,$B$$A$$B$

Das triviale Beispiel eines New-Sense-Universal-Problemlösers ist ein Algorithmus, der einfach seine Eingabe ausführt

Es gibt keinen effizienten universellen Problemlöser. Intuitiv sollte U die (fast) optimale Laufzeit für jedes entscheidbare Entscheidungsproblem haben; während das Beschleunigungs-Theorem besagt, dass es entscheidbare Entscheidungsprobleme gibt, die keinen optimalen Algorithmus haben (nicht einmal in einem sehr milden Sinne). So formalisieren Sie dies:

Das Zeitbeschleunigungs-Theorem (siehe zum Beispiel [1])): Für jede berechenbare (und superlineare) Funktion gibt es eine entscheidbare Menge S, so dass, wenn S ∈ D T I M E ( t ), dann S ∈ D T I M E ( t ' ) für t ' , das g ( t ' ( n ) ) < t ( n ) erfüllt .$g$$S$$S \in DTIME(t)$$S \in DTIME(t')$$t'$$g(t'(n)) < t(n)$

Im Folgenden arbeiten wir mit der zweiten Definition. Sei ein universeller Problemlöser. Sei g ( n ) = 2 2 n und A ein Algorithmus, der S entscheidet . Sei A i die no input TMs st A i = A ( i ) . Es gibt ein TM ˜ U ( i ) = U ( A i ) mit etwa einer logarithmischen Überlastung in der Laufzeit (Die Kodierung von A und A $U$$g(n)=2^{2n}$$A$$S$$A_i$$A_i = A(i)$$\tilde U(i)=U(A_i)$$A$$A_i$unterscheiden sich nur ). Durch die Geschwindigkeitserhöhung thoerem, gibt es eine TM B , der entscheidet , S und 2 2 T I M E ( B ) < T I M E ( ~ U ) . Wir haben also 2 T I M E ( B ) < T I M E ( { U ( A i ) } ) .$O(\log i)$$B$$S$$2^{ 2 TIME(B)} < TIME(\tilde U)$$2^{TIME(B)} < TIME(\{U(A_i)\})$

Sei ein universeller Problemlöser, der für den Eingang A i B ( i ) mit einer logarithmischen zeitlichen Überlastung simuliert . (Offensichtlich sind die Laufzeitfunktionen von A ( i ) und B ( i ) unbegrenzt.) Also haben wir$V$$A_i$$B(i)$$A(i)$$B(i)$

$\forall c \; \exists A_i \;\; t(U, A_i) > t(V, A_i) +c$

So kann nicht effizient sein.$U$

[1] Oded Goldreich, Computational Complexity, A Conceptual Perspective, Theorem 4.8. Kapitel 4.2.1.2 ist ebenfalls relevant.

Der universelle Algorithmus von Levin ist ein Algorithmus, bei dem . Durch Modifizieren des Algorithmus (siehe z. B. Hutters schnellster und kürzester Algorithmus für alle genau definierten Probleme ) können Sie s V zu einer universellen Konstante machen, wenngleich definitiv nicht 1, wie Sie es benötigen. Konsultieren Sie für verwandte Arbeiten die Arbeiten von Hirsch, Itsykson und ihren Schülern, zum Beispiel diesen technischen Bericht .$t(U,A) < s_V t(V,A) + t_V$$s_V$$1$

Bearbeiten: Wie Squark kommentiert, hängt die Laufzeit von Levins Algorithmus auch von der Laufzeit von , da es seine Antworten überprüfen muss. Um eine Konstante s V zu erhalten , müssen Sie lediglich die Geschwindigkeit der verschiedenen Algorithmen in geometrischer Folge einstellen (und nicht in arithmetischer Folge, wie im ursprünglichen Levin-Algorithmus).$A$$s_V$