Por que essa função é computável no tempo

10

Meu livro diz: "Nós definimos a função da seguinte forma: f ( 1 ) = 2 e f ( i + 1 ) = 2 f ( i ) 1.2 . Nota que, dado n , podemos facilmente encontrar em O ( n 1,5 ) tempo o número i de tal modo que n é ensanduichada entre f ( i ) e f ( i + 1f:NNf(1)=2f(i+1)=2f(i)1.2nO(n1.5)inf(i) . "f(i+1)

Como posso me convencer de que podemos de fato muito fácil verificar em O ( n 1,5 ) tempo? Como f é definido recursivamente, acho que temos que calcular f ( 1 ) , f ( 2 ) , f ( 3 ) ... f ( j ) até f ( j ) n . Para descobrir o tempo que esses cálculos levam, acho que precisamos encontrar um limite superior adequado para i dependente de niO(n1.5)ff(1),f(2),f(3)f(j)f(j)nine temos que encontrar um limite superior no tempo de execução da função . No final, podemos mostrar a proposta citada. Infelizmente, não vejo uma coisa nem outra.x2x1.2

Esqueci de mencionar: Por favor, note que estamos em um contexto não determinístico. Portanto, é reivindicada como computável em O ( n 1,5 ) por uma máquina de Turing não determinística.fO(n1.5)


Como algumas pessoas já leram esta pergunta, com algumas achando útil e interessante também, mas ninguém respondeu até agora, desejo fornecer mais informações sobre o contexto: A alegação citada é parte integrante da prova de o teorema da hierarquia de tempo não determinístico. A prova (com a alegação) pode ser encontrada, por exemplo, no livro de Arora e Barak , mas também encontrei muitos outros recursos na Web que apresentam a mesma prova. Cada um deles chama a afirmação de fácil ou trivial e não especifica como encontrar no tempo O ( n 1,5 ) . Portanto, todos esses recursos copiados de Arora e Barak ou a alegação não são tão difíceis.iO(n1.5)

user1494080
fonte
11
Parece a prova do teorema da hierarquia de tempo não determinística em Arora & Barak, não é? Nesse caso, presumo que o não determinismo desempenha um papel aqui.
G. Bach
Você está certo. Desculpe por isso, eu deveria ter mencionado o contexto não determinístico. Você pode explicar com mais detalhes como o não determinismo nos ajuda a mostrar o limite de O (n ^ 1,5)?
user1494080

Respostas:

4

Denotar por o comprimento de um número x , ou seja, log 2 x + 1 (para x > 0 ). Calcular 2 x requer tempo O ( x ) no modelo de RAM e, portanto, calcular f ( i + 1 ) a partir de f ( i ) leva tempo O ( f ( i ) 1,2 ) = O ( | f|x|xlog2x+1x>02xO(x)f(i+1)f(i) . Como f ( i ) está crescendo mais rápido do que geometricamente, o tempo total para calcular f ( i + 1 ) é O ( | f ( i + 1 ) | ) . Como você aponta, você precisa fazê-lo até f ( i + 1 ) n , o que significa que f ( i ) < n . Portanto, o tempo total de execução éO(f(i)1.2)=O(|f(i+1)|)f(i)f(i+1)O(|f(i+1)|)f(i+1)nf(i)<n .O(|f(i+1)|)=O(f(i)1.2)=O(n1.2)

No modelo de máquina de Turing com uma única fita, calcular leva tempo O ( x log x ) e, portanto, o tempo total de execução é O ( n 1,2 log n ) = O ( n 1,5 ) . O algoritmo para calcular 2 x substitui [ x ] por 1 [ [ x ] ] (aqui [ x ] é a representação binária de x , e [ [2xO(xlogx)O(n1.2logn)=O(n1.5)2x[x]1[[x]][x]x é a representação binária usando dígitos diferentes 0 , 1 [[x]]0,1 ) e, em seguida, executa repetidamente a transformação , que leva tempo O ( | x | ) = O ( log x ) .[[x]]0[[x1]]O(|x|)=O(logx)

Yuval Filmus
fonte
Perfeito, obrigado! Mais uma pergunta: não precisamos argumentar que | f (i) | cresce mais rápido que geometricamente ao invés de que f (i) cresce mais rápido que geometricamente?
usuário1494080
|f(i+1)|=f(i)1.2, it's the same thing, but you're right. What we really want is ji|f(j)|=O(|f(i)|).
Yuval Filmus