Grandes classes que contêm LOGSPACE para as quais inclusões estritas são desconhecidas

12

A página da wikipedia no PSPACE menciona que a inclusão não é conhecida por ser rigorosa (infelizmente sem referências).NLPH

Q1: E quanto a e L P # P - estes são conhecidos por serem rigorosos?LPHLP#P

Q2: Se não, existe uma classe estabelecida que contém P # P e para a qual não se sabe se a inclusão L C é estrita?CP#PLC

Q3: tais inclusões são discutidas na literatura?

Łukasz Grabowski
fonte
2
Eu acho que para o Q2 você quer dizer estritamente contido no PSPACE?
Sasho Nikolov
5
AFAIK, a única separação conhecida para é o teorema da hierarquia espacial. Acho que não se sabe se alguma das classes mencionadas na pergunta pode simular o espaço super-logarítmico, de modo que também não se sabe que sejam rigorosas. (Não sabendo uma separação não é um resultado de modo que é provavelmente a razão não há referências.)L
Kaveh
4
Mesmo para classes menores que , como uniform , as inclusões de Q1 não são conhecidas por serem rigorosas. Penso que, dado o estado atual do conhecimento, essencialmente qualquer classe C entre P # P e estritamente contida em P S P A C E é uma resposta positiva para Q2. LNC1CP#PPSPACE
Joshua Grochow
O título da sua pergunta diz "Maior classe". Você não quer dizer "classe menor"?
Shaull
4
Nem se sabe se está estritamente incluído no PH. P # P contém estritamente TC ^ 0 por um argumento de hierarquia, mas como Joshua Grochow já mencionou, isso não é conhecido por NC ^ 1. Para o segundo trimestre, você pode tomar CH. AC0[6]P#P
Emil Jeřábek 3.0 28/08

Respostas:

7

Esta é uma das minhas perguntas favoritas.

Fortnow mostrou, no seu artigo "tempo-espaço Tradeoffs para satisfiability" , que é adequadamente contido em Σ um ( n ) P , em que uma ( n ) é qualquer função ilimitada. Ou seja, o espaço de registro não determinístico está adequadamente contido no tempo polinomial alternado por um (NLΣa(n)Pa(n) alternância.a(n)

Mostrando que não está em Σ k P para uma constante fixa k implicaria que N G NLΣkPk . (Para ver isso, considere o contrapositivo.)NLNP

É aberto se . A última vez que tentei seriamente provar isso, resultou no artigo "Trocas de espaço e tempo para a contagem de números inteiros de módulos da NP Solutions" . Eu estava tentando encontrar alguma simulação de todas as línguas logspace que levaria n k tempo para alguns fixo k quando se tem acesso a um oráculo para contar atribuições que satisfazem a uma determinada fórmula. (Isso implicaria L O G S P A C E NL=P#PnkkLOGSPACEP#P.) Minha abordagem não funcionou, mas acabei usando a mesma abordagem para provar os limites inferiores do tempo-espaço para resolver o e outros resultados relacionados.Mod6SAT

Uniform- é adequadamente contido em P # P . A prova está em Allender, "O Permanente Requer Grandes Circuitos Uniformes de Limiar" . Qualquer melhoria nessa separação está aberta. (Por exemplo, provar uniforme - N C 1P # P está aberto, e provar uniforme - T C 0N P também está aberto.)TC0P#PNC1P#PTC0NP

Ryan Williams
fonte
3
TCo(loglogn)
1
Sim, eu sei sobre esse também, e outras referências também. Mas mantive uma resposta resumida que não levaria mais de 10 minutos para ser escrita.
Ryan Williams