O teorema da hierarquia de tempo afirma que as máquinas de turing podem resolver mais problemas se tiverem (bastante) mais tempo. Isso vale de alguma forma se o espaço é limitado assintoticamente? Como relaciona com se cresce rápido o suficiente?
Estou interessado especialmente no caso em que , e .
Em particular, considerei o seguinte idioma:
No entanto, pode ser decidido em etapas usando .
Sem limitar a quatro símbolos de fita e, assim, permitir comprimir células em células, obtemos problemas de espaço ao simular um com muitos símbolos de fita. Nesse caso, o idioma não está mais em . O mesmo acontece ao definir para alguns que podem ser calculados com rapidez suficiente.
Esta questão é basicamente uma reformulação da minha pergunta aqui .
Resumo de edição: Alterado para , no entanto, acho vale a pena pensar também no cruzamento.
Respostas:
Este é um problema aberto: está aberto se (ou mesmo ). Sabemos apenas que .DTISP(O(nlogn),O(n))=DSPACE(O(n)) NSPACE(O(n)) DTIME(O(n))⊆DSPACE(O(n/logn))
No entanto, sob conjecturas plausíveis de complexidade computacional, existe uma hierarquia adequada. Por exemplo, se para cada , CIRCUIT-SAT ∉ io- , então onde , é , e é tempo-espaço constructible.O ( 2 n - ε )ε>0 O(2n−ε) DTISP(O(f),O(s(n)))⊊DTISP(O(f1+ε),O(s(n)))
f(n)≥n f(n) 2o(min(n,s(n))) f
Em particular (sob a hipótese), a existência de uma atribuição satisfatória para circuitos com entradas e tamanho serve como um contra-exemplo à igualdade das classes.⌊lg(f1+ε/2)⌋ (logf)O(1)
Notas:
CIRCUIT-SAT é pelo menos tão difícil quanto SAT (que é usado na hipótese de tempo exponencial forte).k
Por convenção, em CIRCUIT-SAT, é o número de fios de entrada; o tamanho do circuito é .n nO(1)
Se a suposição usada CIRCUIT-SAT para tamanhos de circuito quase-lineares, o limite em pode ser relaxado para . Além disso, suposições mais fracas / mais fortes sobre a dureza do CIRCUIT-SAT fornecem hierarquias mais fracas / mais fortes (que atualmente podemos provar).f(n) O((2−ε)min(n,s(n)))
io significa infinitamente frequentemente e pode ser descartado para que, em certo sentido, são contínuos (incluindo ).f f(n)=na
Parece provável que a hierarquia do DTISP seja nítida o suficiente para distinguir de (e talvez ) (quando não for muito grande em relação ao espaço permitido).O(f) o(f/logf) o(f) f
Para distinguir de , precisamos apenas da suposição mais fraca P ≠ PSPACE.na 2n
fonte