Unter welchen Umständen implizieren Algorithmen Algorithmen?

Angenommen, für jedes gibt es eine Turingmaschine , die eine Sprache in der Zeit . Gibt es einen einzelnen Algorithmus, der in der Zeit ? (Hier wird der Term in Form von , der Eingabelänge, gemessen .) $\epsilon > 0$ $M_{\epsilon}$ $L$ $O(n^{a + \epsilon})$ $L$ $O(n^{a + o(1)})$ $o(1)$ $n$

Macht es einen Unterschied, ob die Algorithmen in Bezug auf berechenbar oder effizient berechenbar sind ? $M_{\epsilon}$ $\epsilon$

Motivation: In vielen Beweisen ist es einfacher, Algorithmen der Zeit zu konstruieren als den limitierenden Algorithmus . Insbesondere müssen Sie den konstanten Term in begrenzen, um an die Grenze . Es wäre schön, wenn es ein allgemeines Ergebnis gibt, das Sie aufrufen können, um direkt an das Limit zu gelangen. $O(n^{a + \epsilon})$ $O(n^{a + o(1)})$ $O(n^{a + \epsilon})$ $O(n^{a+o(1)})$

cc.complexity-theory asymptotics David Harris
quelle

Antworten:

Die Frage ähnelt der Frage nach der konstruktiven Existenz der Grenze einer Folge von (konstruktiven) Objekten. Wenn Sie diese Objekte (hier ) effizient genug einheitlich konstruieren können, können Sie in der Regel die Existenz der Grenze konstruktiv nachweisen. $M\epsilon$

Angenommen, wir haben ein TM das auf und dessen Laufzeit (auch hier sind die Grenzen einheitlich, zB würde so etwas wie nicht funktionieren). Dann können wir diesen einheitlichen Simulator mit der Funktion kombinieren , um die Maschine , die in der Zeit läuft . $N(k,x)$ $M_{|k|^{-1}}$ $x$ $O(n^{a+|k|^{-1}})+O(|k|)$ $O(2^k.n^{a+|k|^{-1}})$ $(k,x)\mapsto x$ $N(x,x)$ $O(n^{a+o(1)})$

PS: ist etwas mehrdeutig, da asymptotische Notationen verschachtelt sind. Ich interpretiere es als . Außerdem müssen wir nicht zu klein sein, zB mindestens . $O(n^{a+o(1)})$ $n^{a+o(1)}$ $a$ $1$

Kaveh
quelle

Sie können den universellen Suchalgorithmus von Levin verwenden. Angenommen, Sie können irgendwie eine Folge von Algorithmen aufzählen , die bestimmen und jeweils zur Zeit ablaufen . Levins Algorithmus läuft in der Zeit für jedes , wobei eine Konstante in Abhängigkeit von . So wird für jeden , Wenn , wähle und lasse $A_k$ $L$ $C_k n^{a+1/k}$ $T(n) \leq D_k n^{a+1/k}$ $k$ $D_k$ $C_k$ $k$

τ (n) ≜ \frac{\log T (n)}{\log n} - a \leq \frac{\log D_{k} + (a + 1 / k) \log n}{\log n} - a = \frac{\log D_{k}}{\log n} + \frac{1}{k} .

$\tau(n) \triangleq \frac{\log T(n)}{\log n} - a \leq \frac{\log D_k + (a+1/k) \log n}{\log n} - a = \frac{\log D_k}{\log n} + \frac{1}{k}.$

ϵ > 0

$\epsilon>0$

k = ⌈ 2 / ϵ ⌉

$k = \lceil 2/\epsilon \rceil$

N = ⌈ D_{k}^{2 / ϵ} ⌉

$N = \lceil D_k^{2/\epsilon} \rceil$ . Dann für , . Deshalb , und wir erhalten, dass der Levin-Algorithmus in der Zeit läuft .

n \geq N

$n \geq N$

τ (n) \leq ϵ

$\tau(n) \leq \epsilon$

τ (n) \to 0

$\tau(n) \rightarrow 0$

n^{a + τ (n)} = n^{a + o (1)}

$n^{a+\tau(n)} = n^{a+o(1)}$

Yuval Filmus
quelle

Wenn ich Levins Algorithmus verstehe, gilt dies nur für Suchalgorithmen. Dieser Algorithmus würde funktionieren, um eine Funktion zu invertieren , wobei in der Zeit berechnet werden kann .

f

$f$

f

$f$

O (n^{o (a)})

$O(n^{o(a)})$

David Harris

Ich schlage nicht vor, den Levinschen Algorithmus selbst zu verwenden, sondern alle Algorithmen mithilfe der Schwalbenschwanzführung parallel auszuführen, sodass jeder Algorithmus nur durch einen multiplikativen Faktor verlangsamt wird.

A_{k}

$A_k$

Yuval Filmus

@ Yuval, wenn Sie alle Algorithmen miteinander verzahnt haben, wie entscheiden Sie dann, welche Antwort Sie akzeptieren möchten? Bei einem Suchproblem können Sie jede vermeintliche Ausgabe testen, dies ist jedoch im Allgemeinen nicht möglich.

David Harris

Ich akzeptiere die erste Antwort, die erscheint. Wir erhalten die , dass die Algorithmen korrekt entscheiden .

A_{k}

$A_k$

L

$L$

Yuval Filmus