Para cada função computável existe um problema que pode ser resolvido na melhor das hipóteses em ?

19

Para cada função computável existe um problema que pode ser resolvido na melhor das hipóteses em ou existe uma função computável modo que todo problema que pode ser resolvido em possa também pode ser resolvido em tempo? $f$ $\Theta(f(n))$ $f$ $O(f(n))$ $o(f(n))$

Esta pergunta surgiu na minha cabeça ontem. Estou pensando nisso há um tempo, mas não consigo descobrir. Eu realmente não sei como eu pesquisaria isso, então estou perguntando aqui. Aqui está o que eu vim com:

Meu primeiro pensamento foi que a resposta é sim: Para cada função computável o problema "Output pontos" (ou criar uma cadeia com pontos ou o que for) não pode, obviamente, ser resolvido em hora. Portanto, precisamos mostrar apenas que ele pode ser resolvido no tempo . Não tem problema, basta usar o seguinte pseudo-código: $f$ $f(n)$ $f(n)$ $o(f(n))$ $O(f(n))$

x = f(n)
for i from 1 to x:
    output(".")

Claramente, esse algoritmo resolve o problema declarado. E o tempo de execução está obviamente em , então o problema foi resolvido. Isso foi fácil, certo? Exceto que não, não é porque você deve considerar o custo da primeira linha. O tempo de execução do algoritmo acima é apenas em se o tempo necessário para calcular estiver em . Claramente isso não é verdade para todas as funções ¹ . $\Theta(f(n))$ $\Theta(f(n))$ $f(n)$ $O(f(n))$

Portanto, essa abordagem não me levou a lugar algum. Ficaria grato por alguém me apontando na direção certa para descobrir isso corretamente.

¹ Considere, por exemplo, a função . Claramente , mas não há algoritmo que calcule no tempo de . $p(n) = \cases{1 & \text{if $n$ is prime} \\ 2 & \text{otherwise}}$ $O(p(n)) = O(1)$ $p$ $O(1)$

complexity-theory sepp2k
fonte

1

Não acho que suas duas afirmações em seus primeiros parágrafos sejam necessariamente contrapositivas: e se você tiver um tal que exista algum problema que possa ser resolvido em , não em , nem em tempo?

f

$f$

O (f (n))

$O(f(n))$

o (f (n))

$o(f(n))$

Θ (f (n))

$\Theta(f(n))$

Alex ten Brink

@ Alex Esse é um bom ponto que não considerei isso.

sepp2k

13

Pelo teorema de Gap (usando a formulação daqui , procure por 'gap'), para qualquer função ilimitada computável , existe algum aumento (de fato, arbitrariamente grande) computável função modo que . $g : \mathbb{N} \rightarrow \mathbb{N}$ $f : \mathbb{N} \rightarrow \mathbb{N}$ $DTIME(f(n)) = DTIME(g(f(n))$

Isso responde à sua pergunta na medida em que existe um tal (infinitamente muitos, de fato): para toda função computável tal que , existe alguma função crescente tal que todos os problemas solucionáveis em tempo também é solucionável no tempo . Observe que não é necessariamente construtível no tempo - para o caso construtível no tempo, veja a resposta de @RanG. $f$ $g$ $g = o(n)$ $f$ $O(f(n))$ $O(g(f(n)) = o(f(n))$ $f$

Na formulação da Wikipedia (que requer que ), então se torna seu exemplo, precisa ser (para que você faça o contrário - 'problemas solucionáveis em também são solucionáveis em 'é a parte interessante). $g(x) \geq x$ $g \circ f$ $f$ $\omega(n)$ $O(g(f(n))$ $O(g(n))$

O artigo da Wikipedia não observa que está aumentando e pode de fato ser arbitrariamente grande ( por exemplo). O artigo que comprova o teorema do intervalo faz menção e provar isso (ver aqui , por exemplo). $f$ $f(n) \geq g(n)$

Alex ten Brink
fonte

pode ser ? Não é necessário que ? Sua declaração ainda está correta, mas a prova segue para o outro lado, certo?

g

$g$

o (n)

$o(n)$

g (x) \geq x

$g(x)\ge x$

Ran G.

@Tocou. Actualizado a dar uma prova para ambas as formulações (I usado a formulação no papel) :)

Alex dez Brink

"para toda função computável g tal que g = o (n), existe alguma função f tal que todos os problemas solucionáveis no tempo de O (f (n)) também sejam solucionáveis em O (g (f (n)) = o ( f (n)) time "E se todos os fs existentes para esse g estiverem em O (1)? Então O (g (f (n)) ainda é O (1) e, portanto, não o (1).

sepp2k

@ sepp2k: boa captura, este é realmente um problema conforme formulado. Eu atualizei minha resposta.

Alex10 Brink #

12

Para cada função computável existe um problema que pode ser resolvido na melhor das hipóteses em ou existe uma função computável modo que todo problema que pode ser resolvido em possa também pode ser resolvido em tempo? $f$ $\Theta(f(n))$ $f$ $O(f(n))$ $o(f(n))$

Se é uma função construtiva de tempo , o Teorema da Hierarquia de Tempo diz que existem problemas que requerem tempo e não podem ser resolvidos com tempo . Especificamente, $f$ $O(f(n))$ $o\left (\frac{f(n)}{\log(f(n))}\right )$

DTIME (o (\frac{f (n)}{\log (f (n))})) ⊊ DTIME (f (n))

$\text{DTIME}\left ( o\left (\frac{f(n)}{\log(f(n))}\right) \right ) \subsetneq \text{DTIME} \left ( f(n) \right)$

Isso considera apenas problemas de decisão e não considera o tempo necessário para gerar a saída.

Tocou.
fonte

Estou certo ao supor que, se considerarmos funções não construtíveis no tempo, a resposta para minha pergunta é "não"? Ou relacionado: se uma função não é construtível no tempo e, portanto, não existe uma máquina de Turing que pare após etapas, isso significa que também não há uma máquina de Turing que pare após as etapas ? Porque a partir daí seria trivial que a resposta para minha pergunta seja não.

f

$f$

f (n)

$f(n)$

Θ (f (n))

$\Theta(f(n))$

sepp2k

Depende. Suponha que não seja construtível no tempo, mas pode ser limitado por alguma outra função que seja construtível no tempo. e ainda existem problemas que podem ser resolvidos com o tempo mas não muito menos que isso.

f

$f$

g

$g$

f = Θ (g)

$f=\Theta(g)$

O (f)

$O(f)$

Ran G.

e usando várias TMs de fita, é possível melhorar o resultado de para .

o (\frac{f (n)}{\lg f (n)})

$o(\frac{f(n)}{\lg f(n)})$

o (f (n))

$o(f(n))$

Kaveh

3

Vou tentar fornecer uma espécie de estrutura na esperança de que conceda uma visão mais profunda.

Quando você chega a algo tão fundamental, existem armadilhas inesperadas em todos os lugares. Por exemplo: o que é "resolver" um problema? Freqüentemente, na ciência da computação, consideramos apenas a variante "decisão", na qual recebemos uma entrada e precisamos apenas produzir True ou False. Você está se concentrando no problema da "função".

Se você considerar a notação O (f (n)) como tentar capturar quanto "trabalho" é necessário para resolver um problema, usar decisão em vez de função (onde a saída é necessária) parecerá melhor porque você separa claramente o cálculo da formatação da saída .

Acho que isso não vai responder à sua pergunta, mas você pode estar interessado nisso: http://en.wikipedia.org/wiki/Time_hierarchy_theorem

Além disso, tenha cuidado com o teorema da aceleração .

agorenst
fonte

Para cada função computável existe um problema que pode ser resolvido na melhor das hipóteses em ?

Respostas: