Limites inferiores na complexidade do espaço monótono

A complexidade do espaço monótono de uma linguagem pode ser definida em termos de redes de comutação monótonas (consulte, por exemplo, "Limites inferiores médios de caso para redes de comutação monotônicas" por Filmus et al.). Essa noção está vinculada à hierarquia N C monótona e pode ter aplicativos para a configuração não monótona, para a qual a maioria das perguntas está aberta.$L \subseteq \Sigma^*$$NC$

Aqui está uma definição equivalente em termos de circuitos. Seja um circuito (ou dag) cujos arcos sejam rotulados por elementos de [ n ] × Σ e que tenham um único nó raiz r . Nós dizemos que K aceita uma palavra w ∈ Σ n sse existe um caminho de folhas raiz P em K , cuja sequência de partidas etiquetas w , ou seja, para cada etiqueta ( i , a ) em P temos w [ i ] = a . Agora, dado um idioma$K$$[n] \times \Sigma$$r$$K$$w \in \Sigma^n$$P$$K$$w$$(i,a)$$P$$w[i] = a$ , para cada inteiro n , definimos suacomplexidade n- slice C L ( n ) como o tamanho mínimo de um circuito que aceita exatamente as palavras em L ∩ Σ n . Podemos colocar algumas restrições nessa noção, por exemplo, exigindo que os circuitos sejam lidos uma vez, o que significa que cada caminho de aceitação faz um único acesso a uma determinada posição. Isso leva a uma segunda medida de complexidade C ′ L ( n ), que parece mais fácil de analisar, como ilustrado abaixo.$L$$n$$n$$C_L(n)$$L \cap \Sigma^n$$C'_L(n)$

Um exemplo é o problema correspondência perfeita ( ), que pode ser mostrado para ter complexidade monótona C ' P H ( n ) = 2 Ω ( n ) como se segue. Seja P M n a fatia do idioma correspondente aos gráficos bipartidos G com n vértices em cada lado da bipartição (indicado por A , B ). Considere um circuito K aceitando-o. Dado um número inteiro k , deixe P k denotar o conjunto de caminhos de comprimento $PM$$C'_{PM}(n) = 2^{\Omega(n)}$$PM_n$$G$$n$$A,B$$K$$k$$\mathcal{P}_k$$k$em a partir da raiz, e deixá- T K denotam o par de conjuntos ( S , T ) com S ⊆ A , T ⊆ B e | S | = | T | = k . Por monotonicidade, podemos fazer a seguinte suposição:$K$$\mathcal{T}_k$$(S,T)$$S \subseteq A, T \subseteq B$$|S| = |T| = k$

(*) Para cada nó de profundidade k , existe um tuplo t = ( S , T ) ∈ T k tal que cada caminho P ∈ P k levando a u é marcado por uma permutação σ P : S → T .$u$$k$$t = (S,T) \in \mathcal{T}_k$$P \in \mathcal{P}_k$$u$$\sigma_P : S \rightarrow T$

De fato, se houvesse dois caminhos diferentes levando a correspondendo a tuplas diferentes, um deles poderia ser estendido a uma função que não é uma permutação (e, portanto, reconheceria um gráfico de n arestas que não corresponde).$u$$n$

Agora observe que devemos ter a seguinte propriedade "cobertura": para cada permutação , deve existir algum caminho P ∈ P k tal que σ estende σ P . Observe que uma determinada permutação σ P pode ser estendida para no máximo ( n - k ) ! permutações diferentes, e que uma determinada tupla em T k pode induzir no máximo k ! permutações diferentes. Isso implica que o número de nós na profundidade k é pelo menos $\sigma : A \rightarrow B$$P \in \mathcal{P}_k$$\sigma$$\sigma_P$$\sigma_P$$(n-k)!$$\mathcal{T}_k$$k!$$k$. Em particular, o número de nós no nível$\frac{n!}{k! (n-k)!}$ é pelo menosn$\frac{n}{2}$.$\frac{n!}{(\frac{n}{2})!^2} = 2^{\Omega(n)}$

Há duas coisas que eu gostaria de compreender: (i) por que esse raciocínio quebrar para a complexidade do espaço / não monótonas leitura muitos, (ii) como ele se relaciona com limites inferiores conhecidos para a complexidade espaço monótona de .$PM$

Isso não é exatamente uma resposta, mas um "comentário estendido".

Para questionar (i): property (*) é válido por causa da leitura única, não por causa da monotonicidade, e é por isso que o argumento falha no caso de leitura múltipla (mesmo monotônica): os caminhos combinados não precisam ser PMs, eles podem ser gráficos arbitrários contendo um PM.

No caso de leitura única, mesmo o PM exato (aceite um gráfico se for uma correspondência perfeita) requer tamanho exponencial (pelo mesmo argumento que o seu). Mas se permitirmos negações, o EPM pode ser calculado por um circuito do tamanho : verifique se todos os nós em A possuem grau pelo menos um e se todos os nós em B têm grau no máximo um. A rede de comutação resultante é "quase uma só leitura": todo caminho consistente é lido uma vez. Buscar termo "nulo-path" aqui para mais informações. $O(n^3)$

Para a pergunta (ii): não entendi a que "aqui" se refere? Mas, tanto quanto eu sei, o limite inferior de Razborov (para o tamanho de circuito monótono de PM) continua sendo o mais forte. Embora as redes de comutação monotônica constituam um caso especial de circuitos monotônicos (onde uma entrada de cada porta AND deve ser variável), nenhum limite inferior mais forte para PM é conhecido aqui.$n^{\Omega(\log n)}$