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.
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 , 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.
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 kem 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:
(*) 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 .
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).
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 n. Em particular, o número de nós no níveln é pelo menosn!.
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 .
fonte