Em que circunstâncias os algoritmos

16

Suponha que, para cada ϵ>0 , exista uma máquina de Turing Mϵ que decida um idioma L no tempo O(na+ϵ) . Existe um algoritmo único que decide L no tempo O(na+o(1)) ? (Aqui, o(1) termo o ( 1 ) é medido em termos de n , o comprimento da entrada.)

Faz diferença se os algoritmos Mϵ são computáveis ​​ou eficientemente computáveis ​​em termos de ϵ ?

Motivação: em muitas provas, é mais fácil construir algoritmos de tempo O(na+ϵ) que o algoritmo limitador O(na+o(1)) . Em particular, você precisa vincular o termo constante em O(na+ϵ) para passar para o limite O(na+o(1)) . Seria bom se houver algum resultado geral que você possa chamar para passar diretamente para o limite.

David Harris
fonte

Respostas:

10

A questão é semelhante às questões sobre a existência construtiva do limite de uma sequência de objetos (construtivos). Normalmente, se você pode construir uniformemente esses objetos (aqui Mϵ ) com eficiência suficiente, poderá mostrar construtivamente a existência do limite.

Por exemplo, suponha que tenhamos uma TM que executa M | k | - 1 em x e seu tempo de execução é O ( n a + | k | - 1 ) + O ( | k | ) (aqui os limites também são uniformes, por exemplo, algo como O ( 2 k . N a + | k | - 1 )N(k,x)M|k|1xO(na+|k|1)+O(|k|)O(2k.na+|k|1)não funcionaria). Em seguida, pode combinar este simulador uniforme com a função de para obter o máquina N ( x , x ) que é executado no tempo O ( n um + O ( 1 ) ) .(k,x)xN(x,x)O(na+o(1))

PS: é um pouco ambíguo por causa do aninhamento de notações assintóticas, estou interpretando como n a + o ( 1 ) . Também precisamos de um ser não muito pequeno, por exemplo, pelo menos 1 .O(na+o(1))na+o(1)a1

Kaveh
fonte
8

Você pode usar o algoritmo de busca universal de Levin. Suponha que você possa de alguma forma enumerar uma sequência de algoritmos decide L , cada um executando no tempo C k n a + 1 / k . O algoritmo de Levin é executado no tempo T ( n ) D k n a + 1 / k para cada k , onde D k é uma constante, dependendo de C k . Assim, para cada k , τ ( n ) AkLCkna+1/kT(n)Dkna+1/kkDkCkk Dadoϵ>0, escolhak=2/ϵe deixeN=D 2 / ϵ k. Então paranN,τ(n)ϵ. Portantoτ(n)0, e obtemos que o algoritmo de Levin é executado no tempona+τ(n)=na+

τ(n)logT(n)lognalogDk+(a+1/k)lognlogna=logDklogn+1k.
ϵ>0k=2/ϵN=Dk2/ϵnNτ(n)ϵτ(n)0 .na+τ(n)=na+o(1)
Yuval Filmus
fonte
Se eu entendo o algoritmo de Levin, isso se aplica apenas aos algoritmos de pesquisa. Este algoritmo funcionaria para inverter uma função , onde f pode ser calculado no tempo O ( n o ( a ) ) . ffO(no(a))
David Harris
Eu não estou sugerindo usando o algoritmo de Levin em si, apenas a idéia de executar todos os algoritmos em paralelo usando articulação, de tal forma que cada um é retardado apenas por um fator multiplicativo. Ak
Yuval Filmus
@ Yuval, quando você ensina todos os algoritmos, como decide qual resposta aceitar? Em um problema de pesquisa, você pode testar cada saída putativa, mas em geral isso não é possível.
David Harris
Eu aceito a primeira resposta que aparece. Estamos dado que a algoritmos decidir corretamente L . AkL
Yuval Filmus