Clases grandes que contienen LOGSPACE para las cuales se desconocen las inclusiones estrictas

La página de Wikipedia en PSPACE menciona que la inclusión no es estricta (desafortunadamente sin referencias). $NL\subset PH$

P1: ¿Qué pasa con y ? ¿Se sabe que son estrictos? $L\subset PH$ $L\subset P^{\#P}$

P2: Si no, ¿hay una clase establecida que contiene y para la cual no se sabe si la inclusión es estricta? $C$ $P^{\#P}$ $L\subset C$

P3: ¿Se incluyen tales inclusiones en la literatura?

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

¿Supongo que para Q2 te refieres estrictamente a PSPACE?

Sasho Nikolov

AFAIK, la única separación conocida para es el teorema de la jerarquía espacial. No creo que se sepa si alguna de las clases mencionadas en la pregunta puede simular un espacio superlogarítmico, por lo que tampoco se sabe que sean estrictas. (No saber una separación no es un resultado, por lo que probablemente esa sea la razón por la que no hay referencias).

L

$\mathsf{L}$

Kaveh

Incluso para clases más pequeñas que , como uniform , no se sabe que las inclusiones de Q1 sean estrictas. Creo que, dado el estado actual del conocimiento, esencialmente cualquier clase entre y estrictamente contenida en es una respuesta positiva a 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

El título de su pregunta dice "Clase más grande". ¿No te refieres a la "clase más pequeña"?

Shaull

Ni siquiera se sabe si está estrictamente incluido en PH. contiene estrictamente TC ^ 0 mediante un argumento de jerarquía, pero como Joshua Grochow ya mencionó, esto no se conoce para NC ^ 1. Para Q2, puede tomar CH.

A C^{0} [6]

$AC^0[6]$

P^{# P}

$P^{\#P}$

Emil Jeřábek

Respuestas:

Esta es una de mis preguntas favoritas.

Fortnow demostró, en su artículo "Intercambios tiempo-espacio para la satisfacción" , que está contenido adecuadamente en , donde es una función ilimitada. Es decir, el espacio de registro no determinista está contenido adecuadamente en un tiempo polinómico alterno con alternancia. $NL$ $\Sigma_{a(n)} P$ $a(n)$ $a(n)$

Mostrar que no está en para una constante constante implicaría que $NL$ $\Sigma_k P$ $k$ $NL \neq NP$ . (Para ver esto, considere el contrapositivo).

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

T C

$\mathsf{TC}$

o (\log \log n)

$o(\log \log n)$

Sí, también sé sobre eso, y también sobre otras referencias. Pero mantuve una respuesta resumida que no tomaría más de 10 minutos para escribir.

Ryan Williams