Sabemos que . No Teorema de Savitch, e, no Teorema da Hierarquia Espacial, \ mathcal {L} \ neq \ mathcal {L} ^ 2 . Portanto, como não sabemos se \ mathcal L \ neq \ mathcal P , não sabemos se \ mathcal L ^ 2 \ subseteq \ mathcal P , ou sabemos que \ mathcal L ^ 2 \ not \ subseteq \ mathcal P ? Alguém está tentando provar que \ mathcal L ^ 2 \ subseteq \ mathcal P ? Quais são os últimos resultados ou esforços dessa maneira? Eu tenho tentado escrever uma pesquisa sobre este tópico, mas não encontrei nada relevante.NL ≠ L 2 L ≠ P L 2 ⊆ P L 2 ⊈ P L 2 ⊆ P
Além disso, se existe ou não um problema que não é é uma questão em aberto, e essa existência implicaria , como cada problema é completo para . Mas nós realmente não sabemos isso ? Alguém está tentando provar isso? Novamente, quais são os últimos resultados ou esforços dessa maneira?
Talvez esteja faltando alguma coisa ou pesquisando incorretamente, mas não encontrei ninguém trabalhando nas perguntas e .
fonte
Respostas:
Você pode verificar o seguinte documento:
Translational lemas, tempo polinomial, e -espaço(logn)j por Ronald V. Book (1976).
As figuras 1 e 2 do artigo resumem o que é conhecido e o que é desconhecido.
Coloquei o Teorema 3.10 no jornal aqui:
fonte