¿En qué circunstancias los algoritmos implican algoritmos ?

Suponga que, para cada , hay una máquina de Turing que decide un lenguaje en el tiempo . ¿Hay un algoritmo único que decida en el tiempo ? (Aquí, el término se mide en términos de , la longitud de entrada). $\epsilon > 0$ $M_{\epsilon}$ $L$ $O(n^{a + \epsilon})$ $L$ $O(n^{a + o(1)})$ $o(1)$ $n$

¿ Hay alguna diferencia si los algoritmos son computables, o eficientemente computables, en términos de ? $M_{\epsilon}$ $\epsilon$

Motivación: en muchas pruebas, es más fácil construir algoritmos de tiempo que el algoritmo limitante . En particular, debe vincular el término constante en para pasar al límite . Sería bueno si hay algún resultado general que pueda invocar para pasar directamente al límite. $O(n^{a + \epsilon})$ $O(n^{a + o(1)})$ $O(n^{a + \epsilon})$ $O(n^{a+o(1)})$

cc.complexity-theory asymptotics David Harris
fuente

Respuestas:

La pregunta es similar a las preguntas sobre la existencia constructiva del límite de una secuencia de objetos (constructivos). Por lo general, si puede construir esos objetos de manera uniforme (aquí ) de manera suficientemente eficiente, puede mostrar la existencia del límite de manera constructiva. $M\epsilon$

Por ejemplo, suponga que tenemos un TM que ejecuta en y su tiempo de ejecución es (aquí los límites también son uniformes, por ejemplo, algo como no funcionaría). Entonces podemos combinar este simulador uniforme con la función para obtener la máquina que se ejecuta en el tiempo . $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)})$

PD: es un poco ambiguo debido a la anidación de anotaciones asintóticas, lo estoy interpretando como . También necesitamos para ser no demasiado pequeño, por ejemplo al menos . $O(n^{a+o(1)})$ $n^{a+o(1)}$ $a$ $1$

Kaveh
fuente

Puede usar el algoritmo de búsqueda universal de Levin. Suponga que de alguna manera puede enumerar una secuencia de algoritmos deciden , cada uno de los cuales se ejecuta en el tiempo . El algoritmo de Levin se ejecuta en el tiempo para cada , donde es una constante que depende de . Entonces, por cada , Dado , elija , y deje $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$ . Entonces para , . Por lo tanto, , y obtenemos que el algoritmo de Levin se ejecuta en el tiempo .

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
fuente

Si entiendo el algoritmo de Levin, esto solo se aplica a los algoritmos de búsqueda. Este algoritmo funcionaría para invertir una función , donde se puede calcular en el tiempo .

f

$f$

f

$f$

O (n^{o (a)})

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

David Harris el

No estoy sugiriendo usar el algoritmo de Levin en sí mismo, solo la idea de ejecutar todos los algoritmos en paralelo usando cola de milano, de tal manera que cada uno se ralentice solo por un factor multiplicativo.

A_{k}

$A_k$

Yuval Filmus

@ Yuval, cuando combinas todos los algoritmos, ¿cómo decides qué respuesta aceptar? En un problema de búsqueda, puede probar cada salida putativa, pero en general esto no es posible.

David Harris

Acepto la primera respuesta que aparece. Se nos da que los algoritmos decidir correctamente .

A_{k}

$A_k$

L

$L$

Yuval Filmus