Qual é a relação conjeturada entre as linguagens P (PTime) e Tipo 1 (sensível ao contexto)?

10

PCSLPCSL

  • P é o conjunto de todos os idiomas decidíveis em tempo polinomial em uma máquina de Turing determinística, e
  • CSL é a classe de linguagens sensíveis ao contexto, conhecida por ser equivalente a , as linguagens decididas por autômatos com limites lineares.NSPACE(O(n))

Para muitas perguntas abertas, há uma tendência a uma resposta (à la "a maioria dos especialistas acredita que "). Existe algo assim para esta pergunta?PNP

Em particular, a resposta teria consequências inesperadas? Só consigo ver as consequências esperadas (mas não comprovadas):

  • Se , (teorema da hierarquia de espaço), portanto, .PCSLPNSPACE(O(n))NSPACE(O(n2))PPSpace
  • Se , então existe uma língua e, por conseguinte, , portanto, .PCSLlPNSPACE(O(n))lPNLNLP

(Agradecimento: A segunda consequência desses dois foi apontada por Yuval Filmus em /cs/69614/ )

mak
fonte

Respostas:

12

Se , então . Por um argumento de preenchimento, isso implica para cada função superpolinomial bem comportada e a cada . Acredito que não se espera que uma vantagem tão forte do espaço ao longo do tempo. O resultado mais conhecido atualmente nessa direção é devido a Hopcroft, Paul e Valiant.PCSLPDSPACE(n2)

DTIME(t(n))DSPACE(t(n)ϵ)
t(n)ϵ>0
DTIME(t(n))DSPACE(t(n)/logt(n)),
Emil Jeřábek
fonte
Obrigado, aceitei esta resposta agora, embora, dada a natureza dessa pergunta, é claro que ainda sejam bem-vindas respostas adicionais.
MAK