Quais são as subfamílias # P-complete de # 2-SAT?

Versão curta.

A prova original de que # 2-SAT é # P- completo mostra, de fato, que as instâncias de # 2-SAT são monótonas (sem envolver negações de quaisquer variáveis) e bipartidas (o gráfico formado pelas cláusulas sobre o variáveis ​​é um gráfico bipartido) são #P -hard. Assim, os dois casos especiais # 2-MONOTONE-SAT e # 2-BIPARTITE-SAT são #P -hard. Existem outros casos especiais que podem ser caracterizados em termos de propriedades 'naturais' da fórmula, que também são #P -hard?

Versão longa.

O problema 2-SAT é a tarefa de computar - para uma fórmula booleana $\phi$ consiste na conjunção de várias cláusulas, em que cada cláusula é uma disjunção de dois literais ou - o número de cadeias booleanas tal que . Descobrir se existe ou não esse é fácil; mas contar o número de soluções em geral é #P completo, como mostrado por Valiant em A complexidade dos problemas de enumeração e confiabilidade, SIAM J. Comput., 8 , pp. 410-421 .ˉ x j x ∈ { 0 , 1 } n ϕ ( x ) = $x_j$$\bar x_j$$x \in \{0,1\}^n$$\phi(x) = 1$$x$

Para o caso do # 2-SAT em particular, o que Valiant realmente mostra é uma redução para o # 2-SAT da contagem de correspondências (incluindo imperfeitas) em gráficos bipartidos, o que dá origem a instâncias do # 2-SAT com uma estrutura muito particular , do seguinte modo.

1. Primeiro, observe que o problema monótono é equivalente, por substituição, ao problema em que para cada variável , ocorre na fórmula ou ocorre, mas não ambos. Em particular, o problema de "diminuição monótona", no qual apenas as negações ocorrem para cada variável é exatamente tão difícil quanto o caso monótono.x j ϕ ˉ x$x_j$$x_j$$\phi$$\bar x_j$$\bar x_j$

2. Para qualquer gráfico com arestas, podemos construir uma fórmula 2-SAT decrescente de monótonos correspondente a correspondências - coleções de arestas que não compartilham nenhum vértice - atribuindo uma variável a cada aresta, representando se está incluído em um conjunto de arestas; a propriedade de um conjunto sendo uma correspondência é equivalente ao vetor de incidência satisfaz a fórmula CNF cujas cláusulas são dadas por para cada par de arestas que compartilham um vértice. Por construção, tem tantas soluções satisfatóriasm X e M ⊆ E x = χ M φ ( ˉ x e ∨ ˉ x f ) e , f ∈ $G = (V,E)$$m$$x_e$$M \subseteq E$$\mathbf x = \chi_M$$\phi$$(\bar x_e \vee \bar x_f)$$e, f \in E$x ∈ { 0 , 1 } $\phi$$\mathbf x \in \{0,1\}^m$uma vez que existem (possivelmente imperfeitos) emparelhamentos no gráfico .$G$

3. Se o gráfico para o qual queremos contar as correspondências for bipartido, ele não conterá ciclos ímpares - que podemos descrever como uma sequência de arestas no gráfico que começa e termina com a mesma aresta (sem contar essa aresta duas vezes) . Então não há sequência de variáveis de comprimento ímpar em , na qual variáveis ​​adjacentes estão envolvidas em uma cláusula comum. Então a fórmula seria bipartida da maneira descrita anteriormente.$G$ ϕ $x_e, x_f, x_g, \ldots, x_e$$\phi$$\phi$

4. A contagem do número de combinações em gráficos bipartidos arbitrários, em particular, pode ser usada para contar o número de combinações perfeitas em um gráfico bipartido: dada uma entrada de gráfico de bitrarita com duas bipartições de o mesmo tamanho , pode-se criar gráficos aumentando com qualquer lugar vértices adicionais ligados a todos os vértices de . Como todas as correspondências em de um determinado tamanho contribuem de maneira diferente para o número de correspondências em , contando-as, é possível determinar o número de correspondências em de tamanho$G = (A \cup B, E)$$A, B$$n$$G_k$$A$$0 \leqslant k \leqslant n$$B$$G$$G_k$$G$$n$(ou seja, combinações perfeitas); e observe que contar o número de combinações perfeitas em gráficos bipartidos é equivalente a calcular permanentes de -matrices por uma correspondência simples.$\{0,1\}$

A classe de instâncias de # 2-SAT que são mostradas como #P -hard são as instâncias bipartidas monótonas.

Pergunta: Quais são os outros casos especiais de # 2-SAT que são # P- completos, como resultado dessa ou de outra redução?

Seria interessante se, além de mostrar / citar uma redução, as pessoas também pudessem descrever uma razão intuitiva de como o caso especial poderia fornecer obstáculos às abordagens naturais para contar as atribuições de classificação. Por exemplo, embora o MONOTONE-2-SAT seja trivialmente solucionável ( é sempre uma solução), instâncias monótonas são aquelas nas quais atribuir uma variável a um valor fixo falhará rotineiramente em impor muitas restrições ao restante variáveis. A qualquer variável restringe apenas os valores das variáveis ​​imediatamente relacionadas a ela por alguma cláusula; e definindo$\mathbf x = 1^n$$x_j = 0$$x_j = 1$não restringe os possíveis valores de quaisquer outras variáveis. (Não está claro que a restrição comparável aos gráficos bipartidos seja significativa da mesma maneira; no entanto, a restrição bipartida parece adicionar estrutura ao invés de removê-la, mas falha ao adicionar estrutura suficiente para contar com eficiência.)

Editado para adicionar. Os pontos de bônus serão concedidos para qualquer classe que não dependa da existência de instâncias monótonas (como o número 2-BIPARTITE-SAT acima, cuja dureza é aparentemente devida à inclusão do caso especial #P -hard nº 2 -MONOTONE-BIPARTITE-SAT). Por exemplo, um argumento para a dureza de # 2-BIPARTITE-SAT que não depende de instâncias monotônicas (mas pode depender de alguma outra subfamília) seria interessante.

# 3-A cobertura planar bipartida regular de vértice é # P-Complete

Como contar capas de vértices é exatamente o mesmo que contar atribuições satisfatórias de uma instância monótona # 2-SAT, o resultado acima implica que é # P-complete contar atribuições satisfatórias de uma instância # 2-SAT monótona e regular e bipartido e plano .

Por sua vez, isso significa que, além dos dois casos especiais # 2-MONOTONE-SAT e # 2-BIPARTITE-SAT já citados na pergunta, os dois casos especiais # 2-CUBIC-SAT e # 2-PLANAR-SAT são # P-completo também.