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

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

Q1: E quanto a e - estes são conhecidos por serem rigorosos? $L\subset PH$ $L\subset P^{\#P}$

Q2: Se não, existe uma classe estabelecida que contém e para a qual não se sabe se a inclusão é estrita? $C$ $P^{\#P}$ $L\subset C$

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

cc.complexity-theory complexity-classes logspace Łukasz Grabowski
fonte

Eu acho que para o Q2 você quer dizer estritamente contido no PSPACE?

Sasho Nikolov

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

$\mathsf{L}$

Kaveh

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

entre

e estritamente contida em

é uma resposta positiva para Q2.

L

$\mathsf{L}$

{N C}^{1}

$\mathsf{NC}^1$

C

$C$

P^{# P}

$\mathsf{P}^{\mathsf{\# P}}$

P S P A C E

$\mathsf{PSPACE}$

Joshua Grochow

O título da sua pergunta diz "Maior classe". Você não quer dizer "classe menor"?

Shaull

Nem se sabe se

está estritamente incluído no PH.

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.

A C^{0} [6]

$AC^0[6]$

P^{# P}

$P^{\#P}$

Emil Jeřábek 3.0 28/08

Respostas:

Esta é uma das minhas perguntas favoritas.

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

Mostrando que não está em para uma constante fixa implicaria que $NL$ $\Sigma_k P$ $k$ . (Para ver isso, considere o contrapositivo.) $NL \neq NP$

É 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 tempo para alguns fixo quando se tem acesso a um oráculo para contar atribuições que satisfazem a uma determinada fórmula. (Isso implicaria $NL = P^{\#P}$ $n^k$ $k$ $LOGSPACE \neq P^{\#P}$ .) Minha abordagem não funcionou, mas acabei usando a mesma abordagem para provar os limites inferiores do tempo-espaço para resolver e outros resultados relacionados. $Mod_6 SAT$

Uniform- é adequadamente contido em . A prova está em Allender, "O Permanente Requer Grandes Circuitos Uniformes de Limiar" . Qualquer melhoria nessa separação está aberta. (Por exemplo, provar uniforme - está aberto, e provar uniforme - também está aberto.) $TC^0$ $P^{\#P}$ $NC^1 \neq P^{\#P}$ $TC^0 \neq NP$

Ryan Williams
fonte

T C

$\mathsf{TC}$

o (\log \log n)

$o(\log \log n)$

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