Uma separação explícita entre construtibilidade no tempo e construtibilidade no espaço?

Mostre uma função que é construtível no espaço, mas não no tempo.$f(n)$

Esse problema está relacionado a uma possível separação entre as classes de complexidade DTIME (f (n)) e SPACE (f (n))?

Uma função é construtível no tempo se houver uma máquina de Turing M que, na entrada 1 n , calcule a função x ↦ T ( | x | ) no tempo O ( T ( n ) ) .$T \colon \mathbb{N} \to \mathbb{N}$$M$$1^n$$x \mapsto T(|x|)$$O(T(n))$

Uma função é espaço construtível se houver uma máquina de Turing M que, na entrada 1 n , calcule a função x ↦ S ( | x | ) no espaço O ( S ( n ) ) .$S \colon \mathbb{N} \to \mathbb{N}$$M$$1^n$$x \mapsto S(|x|)$$O(S(n))$

Alguns textos exigem que as funções construtivas de tempo / espaço não sejam decrescentes. Alguns textos requerem que as funções construtivas no tempo satisfaçam , e as funções construtivas no espaço satisfaçam S ( n ) ≥ log n . Alguns textos não fazem uso da notação O ( ⋅ ) na definição.$T(n)\ge n$$S(n)\ge \log n$$O(\cdot)$

De qualquer forma, é fácil mostrar que todos os "normais" função , satisfazendo f ( n ) ≥ log n e f ( n ) = O ( n ) é constructible espaço, mas não constructible tempo.$f$$f(n)\ge \log n$$f(n) = o(n)$

O problema da construtibilidade não está diretamente relacionado à possível separação entre as classes de complexidade DTIME (f (n)) e SPACE (f (n)). No entanto, a declaração dos teoremas da hierarquia do tempo e do espaço incorpora a construtibilidade. Por exemplo:

Teorema da Hierarquia de Tempo Se , g são funções construtíveis de tempo que satisfazem f ( n ) log f ( n ) = o ( g ( n ) ) , então D T I M E ( f ( n ) ) é um subconjunto adequado de D T I M E ( g ( n ) ) .$f$$g$$f(n)\log f(n) = o(g(n))$$\mathbf{DTIME}(f(n))$$\mathbf{DTIME}(g(n))$

Veja o livro de Arora & Barak ou o de Papadimitriou para obter mais informações. (O último usa o termo "função de complexidade adequada" para se referir a um que é construtível no tempo e no espaço)

é um espaço construtível, mas não um tempo construtível. O motivo é que você pode mapear 1 n para a representação binária no espaço O ( log n ), mas não no tempo O ( log n ) .$f(n)=\log n$$1^n$$O(\log n)$$O(\log n)$

Se todas as funções de espaço-tempo são construtıvel-construtıvel, então . Para provar que (e para dar um exemplo de um não-trivial espaço-construtıvel mas presumivelmente não tempo-construtıvel função), tomemos um arbitrário (possivelmente E X P - S P A C E - C O M P G E T E ) problema L ∈ E X $EXP-TIME=EXP-SPACE$$EXP-SPACE-COMPLETE$ , G ⊆ { 0 , 1 } * . Então existe um k ∈ N , st L pode ser resolvido por um DTM M em um espaço de 2 n k . Agora defina a função f ( n ) = { 8 n + 2 se  ( primeiro  ⌊ k $L\in EXP-SPACE$$L\subseteq\{0,1\}^*$$k\in\mathbb{N}$$L$$M$$2^{n^k}$

$2n$$f$$f$$L$

Esta resposta usa a mesma ideia.