Límites inferiores en la complejidad del espacio monótono

La complejidad del espacio monótono de un lenguaje se puede definir en términos de redes de conmutación monótonas (véase, por ejemplo, "Límites inferiores a mayúsculas y minúsculas para redes de conmutación monótonas" de Filmus et al.). Esta noción está vinculada a la jerarquía monótona N C y puede tener aplicaciones para la configuración no monótona para la que están abiertas la mayoría de las preguntas.$L \subseteq \Sigma^*$$NC$

Aquí hay una definición equivalente en términos de circuitos. Sea un circuito (o dag) cuyos arcos están etiquetados por elementos de [ n ] × Σ , y que tiene un solo nodo raíz r . Decimos que K acepta una palabra w ∈ Σ n si hay una ruta de hoja raíz P en K cuya secuencia de etiquetas coincide con w , es decir, para cada etiqueta ( i , a ) en P tenemos w [ i ] = a . Ahora, dado un idioma$K$$[n] \times \Sigma$$r$$K$$w \in \Sigma^n$$P$$K$$w$$(i,a)$$P$$w[i] = a$ , para cada número entero n definimos sucomplejidad n- corte C L ( n ) como el tamaño mínimo de un circuito que acepta exactamente las palabras en L ∩ Σ n . Podemos imponer algunas restricciones a esta noción, por ejemplo, exigiendo que los circuitos se lean una vez, lo que significa que cada ruta de aceptación hace un acceso único a una posición determinada. Esto lleva a una segunda medida de complejidad C ' L ( n ) que parece más fácil de analizar, como se ilustra a continuación.$L$$n$$n$$C_L(n)$$L \cap \Sigma^n$$C'_L(n)$

Un ejemplo es el problema Perfect Matching ( ), que se puede demostrar que tiene una complejidad monótona C ′ P M ( n ) = 2 Ω ( n ) de la siguiente manera. Supongamos que P M n denota la porción del lenguaje correspondiente a los gráficos bipartitos G con n vértices a cada lado de la bipartición (denotado por A , B ). Considere un circuito K que lo acepte. Dado un entero k , dejemos que P k denote el conjunto de caminos de longitud $PM$$C'_{PM}(n) = 2^{\Omega(n)}$$PM_n$$G$$n$$A,B$$K$$k$$\mathcal{P}_k$$k$en partir de la raíz, y deje que T k denote el par de conjuntos ( S , T ) con S ⊆ A , T ⊆ B y | S | = | T | = k . Por monotonicidad, podemos hacer la siguiente suposición:$K$$\mathcal{T}_k$$(S,T)$$S \subseteq A, T \subseteq B$$|S| = |T| = k$

(*) Para cada nodo de profundidad k , existe una tupla t = ( S , T ) ∈ T k de tal manera que cada trayectoria P ∈ P k conduce a u está marcado por una permutación σ P : S → T .$u$$k$$t = (S,T) \in \mathcal{T}_k$$P \in \mathcal{P}_k$$u$$\sigma_P : S \rightarrow T$

En efecto, si había dos caminos diferentes que conducen a correspondientes a diferentes tuplas, uno de ellos podría extenderse a una función que no es una permutación (y por tanto reconocería un n gráfico -edges que no es una coincidencia).$u$$n$

Ahora observar que debemos tener la siguiente propiedad "cobertura": para cada permutación , debe existir algún camino P ∈ P k tal que σ se extiende σ P . ¡Observe que una permutación dada σ P puede extenderse como máximo ( n - k ) ! diferentes permutaciones, y que una tupla dada en T k puede inducir como máximo k ! diferentes permutaciones Esto implica que el número de nodos a profundidad k es al menos $\sigma : A \rightarrow B$$P \in \mathcal{P}_k$$\sigma$$\sigma_P$$\sigma_P$$(n-k)!$$\mathcal{T}_k$$k!$$k$. En particular, el número de nodos en el nivel$\frac{n!}{k! (n-k)!}$ es al menosn$\frac{n}{2}$.$\frac{n!}{(\frac{n}{2})!^2} = 2^{\Omega(n)}$

Hay dos cosas que me gustaría comprender: (i) ¿Por qué romper este razonamiento hacia abajo para / nonmonotone complejidad espacial muchos leen, (ii) ¿Cómo se relaciona a límites inferiores conocidos de la complejidad del espacio monótona de .$PM$

Esta no es una respuesta, sino un "comentario extendido".

Para la pregunta (i): la propiedad (*) se cumple debido a la lectura única, no debido a la monotonicidad, y esta es la razón por la cual el argumento falla en el caso de lectura múltiple (incluso monotono): entonces las rutas combinadas no necesitan ser PMs, pueden ser gráficos arbitrarios que contienen un PM.

$O(n^3)$

$n^{\Omega(\log n)}$