Definições equivalentes de construtibilidade temporal

Dizemos que uma função é construtível no tempo , se existir uma máquina de Turing determinística múltiplas fitas que em todas as entradas de comprimento faça no máximo etapas e para cada existe alguma entrada de comprimento na qual executa exatamente etapas. M n f ( n ) n n M f ( n $f:\mathbb{N}\rightarrow\mathbb{N}$$M$$n$$f(n)$$n$$n$$M$$f(n)$

Dizemos que uma função é totalmente construtível no tempo , se existir uma máquina de Turing determinística várias fitas que em todas as entradas de comprimento faça exatamente etapas . M n f ( n $f:\mathbb{N}\rightarrow\mathbb{N}$$M$$n$$f(n)$

Q1: Existe uma função que seja construtível no tempo e não totalmente construtível no tempo?

A resposta é sim (veja esta resposta ), se . A condição para "sim" pode ser reforçada para ? O "sim" pode ser provado?P ≠ N $EXP-TIME \neq NEXP-TIME$$P\neq NP$

P2: A classe de funções (totalmente) constitutivas no tempo muda se permitirmos apenas máquinas de Turing com 2 fitas na definição?

Q3: Quais são as razões "prováveis" para acreditar que todas as funções legais são totalmente construtíveis no tempo?

O artigo
Kojiro Kobayashi: Provando a Construtibilidade de Funções no Tempo. Theor. Comput. Sci. 35: 215-225 (1985)
responde parcialmente a Q3. O resumo parcial e a atualização estão nesta resposta . Eu tomo Q3 como respondido.

Historicamente, a noção de função contável em tempo real foi usada em vez de (totalmente) construtiva em tempo. Veja esta pergunta para mais.

Nos últimos dias, pensei muito em funções (totalmente) construtivas no tempo e apresentarei o que descobri respondendo ao Q1 e Q3. Q2 parece muito difícil.

Q3:

Kobayashi em seu artigo (a referência está na pergunta) provou que uma função , para a qual existe um ϵ > 0 st f ( n ) ≥ ( 1 + ϵ ) n , é totalmente construtível no tempo se for computável em O ( f ( n ) ) tempo. (observe que é irrelevante se a entrada ou a saída está em unário / binário, pois podemos transformar entre essas duas representações em tempo linear). Isso torna as seguintes funções totalmente construtíveis no tempo: 2 n ,$f:\mathbb{N}\rightarrow\mathbb{N}$$\epsilon>0$$f(n)\geq (1+\epsilon)n$$O(f(n))$$2^n$ , n ! , N ⌊ log n ⌋ , todos os polinómios de p mais de N r p ( n ) ≥ ( 1 + ε ) n ... Kobayashi também se provou ser totalmente tempo-construtibilidade para algumas funções que crescem mais lentamente do que ( 1 + ε ) n , como n + ⌊ ⌊ log n ⌋ q ⌋ para q ∈ Q + ...$2^{2^n}$$n!$$n\lfloor \log n \rfloor$$p$$\mathbb{N}$$p(n)\geq (1+\epsilon)n$$(1+\epsilon)n$$n+\lfloor\lfloor\log n\rfloor^q\rfloor$$q\in\mathbb{Q}^+$

Para continuar com exemplos de funções totalmente construtíveis no tempo, pode-se provar que, se e f 2 são totalmente construtíveis no tempo, então f 1 + f 2 , f 1 f 2 , f f 2 1 e f 1 ∘ f 2 são também totalmente construtível no tempo (a seguir segue diretamente do Teorema 3.1 em Kobayashi). Isso me convence de que muitas funções agradáveis ​​são de fato totalmente construtíveis no tempo.$f_1$$f_2$$f_1+f_2$$f_1f_2$$f_1^{f_2}$$f_1\circ f_2$

É surpreendente que Kobayashi não tenha visto uma maneira de provar totalmente a construtibilidade no tempo da função (agradável) (e nem eu).$\lfloor n\log n\rfloor$

Vamos também comentar a definição do artigo da Wikipedia : Uma função é construtível no tempo, se existe uma máquina de Turing M que, dada uma string 1 n , gera f ( n ) no tempo O ( f ( n ) ) . $f$$M$$1^n$$f(n)$$O(f(n))$ Vemos que esta definição é equivalente à nossa definição de construtibilidade no tempo total para as funções .$f(n)\geq (1+\epsilon)n$

Q1:

Esta pergunta tem uma resposta realmente interessante. I afirmam que, se todas as funções de tempo-construtıvel são totalmente tempo-construtıvel, então . Para provar isso, tomemos um problema arbitrário L ∈ N E X P - T I M E , L ⊆ { 0 , 1 } ∗ . Então existe um k ∈ N , st $EXP-TIME=NEXP-TIME$$L\in NEXP-TIME$$L\subseteq\{0,1\}^*$$k\in\mathbb{N}$$L$pode ser resolvido por um NDTM em 2 n k - 1 passos. Podemos supor que a cada passo M entre no máximo dois estados diferentes para simplificar. Agora defina a função f ( n ) = { 8 n + 2 se  ( primeiro  ⌊ k $M$$2^{n^k-1}$$M$

Afirmo que é construtível no tempo. Considere a seguinte máquina de Turing determinística T :$f$$T$

• na entrada de comprimento n calcula ( primeiro  ⌊ k $w$$n$emO(n)tempo$\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$$O(n)$
• depois simula nesses bits, onde os bits de w determinam quais escolhas (anteriormente não determinísticas) devem ser tomadas.$M$$w$
• aceite iff .$\left(M\textrm{ accepts using choices given by }w\right)$

Observe que o comprimento de ( = n ) é suficiente para determinar todas as opções não determinísticas, pois M na entrada ( primeiro  ⌊ k $w$$=n$$M$realiza no máximonetapas.$\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$$n$

Podemos fazer o rodar no máximo 8 n + 1 etapas. Agora, a seguinte máquina de Turing prova que f é construtível no tempo:$T$$8n+1$$f$

• na entrada de comprimento n, execute T e conte os passos em paralelo para que sejam executados exatamente 8 n passos.$w$$n$$T$$8n$
• se rejeitou ou rejeitaria na próxima etapa, vá para um estado de parada na próxima etapa. Senão, dê mais um passo e depois pare.$T$

Agora, suponha que seja totalmente construtível no tempo. Vamos provar que isto conduz a E X P - T I M E = N E X P - T I M E .$f$$EXP-TIME=NEXP-TIME$

O seguinte algoritmo resolve :$L$

• na entrada , seja n o número com representação binária x 00 … 0 ( | x | k - 1 zeros). Segue que x = ( primeiro  ⌊ k $x$$n$$x00\ldots 0$$|x|^{k-1}$.$x=\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$
• calcule no tempo f ( n ) e verifique se é divisível por 2.$f(n)$$f(n)$

Este algoritmo é executado em exponencial tempo e resolve . Uma vez que L ∈ N E X P - T I M E foi arbitrária, E X P - T I M E = N E X P - T I M E .$L$$L\in NEXP-TIME$$EXP-TIME=NEXP-TIME$