¿Qué tiene de malo este uniform ?

No se cree que lo siguiente sea cierto:

$\mathsf{L} \subseteq \mathsf{L}-\mbox{uniform } \mathsf{NC}^1$

¿Puedes ayudarme a ver dónde se rompe la discusión?

El problema de accesibilidad dirigida está completo para . Sostengo que está en -uniform . $\mathsf{L}$ $\mathsf{L}$ $\mathsf{NC^1}$

El problema de accesibilidad dirigida sobre los gráficos de configuración de la máquina de Turing de espacio de registro determinista está completo para . $\mathsf{L}$

El problema de accesibilidad dirigida está en : $\mathsf{MSO}_2$

dados y , permiten representa la libre variable para los bordes de la ruta. Necesitamos verificar que contenga una ruta dirigida de a que se puede hacer verificando que el grado de entrada y salida (en ) de cada vértice incidente en un borde en es excepto y que tener en-grado, fuera-grado = y respectivamente. $s$ $t$ $P$ $\mathsf{MSO}$ $P$ $s$ $t$ $P$ $P$ $1$ $s$ $t$ $0,1$ $1,0$

Cada bosque es un gráfico de ancho de árbol . En particular, el gráfico de configuración de una máquina de Turing determinista con espacio de registro es una estructura acotada de ancho de árbol. $1$

De las versiones de Elberfeld, Jakoby y Tantau's Logspace de los teoremas de Bodlaender y Courcelle :

$\mathsf{MSO}$ fórmula sobre estructuras de ancho de árbol acotado puede evaluarse en el espacio logarítmico.

La prueba es más o menos así: para un tamaño de estructura dado , un límite en el ancho del árbol de las estructuras , y una fórmula con vocabulario , construcción (en ) construir un circuito . $n$ $w$ $\mathsf{MSO}$ $\varphi$ $\tau$ $\mathsf{L}$ $\#\mathsf{NC}^1$ $C$

El circuito da una estructura de tamaño y el árbol de ancho, como máximo, , cuenta el número de "satisfactorio" asignaciones de en . $C$ $M$ $n$ $w$ $\varphi$ $M$

(El histograma tabula el número de asignaciones a las variables libres de segundo orden en parametrizadas en los tamaños de los conjuntos de valores tomados por las variables). $\varphi$

Creo que el circuito solo depende del vocabulario , el ancho de árbol enlazado , y el tamaño de la estructura . $C$ $\tau$ $d$ $n$

La prueba procede evaluando el circuito en pero no necesitamos esa parte. $\#\mathsf{NC}^1 \subseteq \mathsf{L}$

Para nosotros es suficiente observar que desde Nondeterministic Computación $\mathsf{NC^1}$ de Caussinus-Mackenzie-Therien-Vollmer:

cada -circuit se puede interpretar como contar el número de árboles de prueba de un -circuit. $\#\mathsf{NC}^1$ $\mathsf{NC}^1$

Por lo tanto, el circuito correspondiente emite si la estructura de entrada satisface la fórmula . $1$ $\mathsf{MSO}$

De lo anterior parece que el espacio logarítmico está al menos en logspace-uniform $\mathsf{NC}^1$

cc.complexity-theory graph-algorithms complexity-classes descriptive-complexity finite-model-theory SamiD
fuente

Su argumento de accesibilidad de MSO no es del todo correcto: solo funcionará si el subgrafo inducido por los vértices es una ruta dirigida, que no es el caso en general (un contraejemplo trivial es un par simétrico de bordes dirigidos). La forma correcta de lograr la accesibilidad en MSO es afirmar que cada conjunto de vértices que contiene está cerrado bajo la relación de borde también incluye .

P

$P$

s

$s$

t

$t$

David Richerby

@SamiD Di el contraejemplo más pequeño, que resulta ser un gráfico simétrico. Pero el gráfico de 3 vértices con bordes dirigidos , , funciona igual de bien: la ruta dirigida única de a es pero el conjunto no satisface su fórmula porque, en el subgrafo inducido por (que es el gráfico completo), no tiene cero grados y no tiene cero grados.

a \to b

$a\to b$

b \to c

$b\to c$

c \to a

$c\to a$

a

$a$

c

$c$

a b c

$abc$

{a, b, c}

$\{a,b,c\}$

{a, b, c}

$\{a,b,c\}$

a

$a$

c

$c$

David Richerby

@David Point bien hecho - mi formulación original tenía errores - Espero que este esté bien: considero un conjunto de bordes en lugar de vértices y miro el grado de vértices en estos bordes - deben ser los mismos que antes. Gracias por el ejemplo

SamiD

@Kaveh Gracias por los cambios, hacen que la pregunta sea más legible. Aclaré el problema que planteó: en mi opinión, EJT crea un circuito aritmético de profundidad logarítmica en L y luego el problema cae en L debido a la contención de CMTV # NC1 \ subseteq L. Pero nos detenemos en el punto en que el circuito se crea y sintácticamente conviértalo a un circuito NC ^ 1. La conversión, etc. se puede hacer fácilmente. Convertí NC ^ 1 / poly a L-uniform NC ^ 1 también porque es más preciso.

SamiD

@Kaveh: 1. Cambiar cada de -circuito a y a creará un circuito tal que cuente el número de árboles de prueba de .

+

$+$

# N C^{1}

$\#NC^1$

C

$C$

\lor

$\vee$

*

$*$

\land

$\wedge$

N C^{1}

$NC^1$

C^{'}

$C'$

C

$C$

C^{'}

$C'$

SamiD

¿Qué tiene de malo este uniform ?

Respuestas: