Grandes classes contenant LOGSPACE pour lesquelles des inclusions strictes sont inconnues

La page wikipedia sur PSPACE mentionne que l'inclusion n'est pas connue pour être stricte (malheureusement sans références). $NL\subset PH$

Q1: Qu'en est-il de et - sont-ils connus pour être stricts? $L\subset PH$ $L\subset P^{\#P}$

Q2: Si non, existe-t-il une classe établie qui contient et pour laquelle on ne sait pas si l'inclusion est stricte? $C$ $P^{\#P}$ $L\subset C$

Q3: Ces inclusions sont-elles discutées dans la littérature?

cc.complexity-theory complexity-classes logspace Łukasz Grabowski
la source

Je suppose que pour Q2 vous voulez dire strictement contenu dans PSPACE?

Sasho Nikolov

AFAIK, la seule séparation connue pour

est le théorème de la hiérarchie spatiale. Je ne pense pas que l'on sache si l'une des classes mentionnées dans la question peut simuler un espace super-logarithmique, de sorte qu'elles ne sont pas connues pour être strictes. (Ne pas connaître une séparation n'est pas un résultat, c'est probablement la raison pour laquelle il n'y a pas de références.)

L

$\mathsf{L}$

Kaveh

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}$

Le titre de votre question indique "Plus grande classe". Vous ne voulez pas dire "la plus petite classe"?

Shaull

A C^{0} [6]

$AC^0[6]$

P^{# P}

$P^{\#P}$

Réponses:

C'est ma question préférée.

$NL$ $\Sigma_{a(n)} P$ $a(n)$ $a(n)$

$NL$ $\Sigma_k P$ $k$ $NL \neq NP$

$NL = P^{\#P}$ $n^k$ $k$ $LOGSPACE \neq P^{\#P}$ $Mod_6 SAT$

$TC^0$ $P^{\#P}$ $NC^1 \neq P^{\#P}$ $TC^0 \neq NP$

Ryan Williams
la source

T C

$\mathsf{TC}$

o (\log \log n)

$o(\log \log n)$

Ouais, je connais celui-là aussi, et d'autres références aussi. Mais j'ai gardé une réponse sommaire qui ne prendrait pas plus de 10 minutes à écrire.

Ryan Williams