Effizienter universeller Problemlöser?

12

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ür1nNnA

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).UU1

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 wurdeUAt(U,A)UA

Ein universeller Problemlöser wird "effizient" genannt, wenn wir für jeden universellen Problemlöser habenUV

t(U,A)<t(V,A)+tV

Hier hängt von , aber nicht vontVVA

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) )ABA

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 ,BAB

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

Vanessa
quelle

Antworten:

5

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 .gSSDTIME(t)SDTIME(t)tg(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 iUg(n)=22nASAiAi=A(i)U~(i)=U(Ai)AAiunterscheiden 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(logi)BS22TIME(B)<TIME(U~)2TIME(B)<TIME({U(Ai)})

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 wirVAiB(i)A(i)B(i)

cAit(U,Ai)>t(V,Ai)+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.

Ruhollah Majdoddin
quelle
Tolle Lösung, danke!
Vanessa
12

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)<sVt(V,A)+tVsV1

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).AsV

Yuval Filmus
quelle
1
Wenn ich das richtig verstehe, ist Levins etwas in der Art von "Lassen Sie uns alle möglichen Algorithmen parallel ausführen und jedes Mal, wenn eine von ihnen eine Antwort erzeugt, testen wir es und halten an, ob es richtig ist". Da V einer der Algorithmen ist, die U ausführt, findet es die Antwort in derselben Zeit wie V bis zu einer Verlangsamung, die sich auf den Bruchteil der "CPU-Zeit" bezieht, die dem "Thread" von V zugewiesen ist. Ich denke jedoch, dass Ihnen ein zusätzlicher A-abhängiger Begriff fehlt: die Zeit, die zum Testen der Antwort erforderlich ist. Hutters Algorithmus stützt sich auf eine Beweissuche, die mir nicht ausreicht, da ich keine Annahmen über die Beweisbarkeit macheU
Vanessa
1
Yuval, mir fehlt etwas. Inwiefern wird konstant? Es hängt immer noch von V ab, da verschiedene Algorithmen mit unterschiedlicher Geschwindigkeit ausgeführt werden, unabhängig davon, welchen Fortschritt Sie verwenden, oder? sVV
Vanessa
Ich glaube, dass man (gleichmäßig) binden kann , um t V noch wilder wachsen zu lassen (aber für jedes gegebene V immer noch konstant ). sVtVV
Yuval Filmus
1
Ich verstehe nicht wie. Übrigens, wenn ich hinzufüge, dass die Bedingung V nachweislich ein universeller Problemlöser ist, wäre es möglich, den A-abhängigen Term zu eliminieren, indem nur Algorithmen ausgeführt werden, die nachweislich universelle Problemlöser sind
Vanessa