Considere uma fórmula Monotone 3CNF com as duas restrições adicionais a seguir:
- Cada variável aparece em exatamente cláusulas.
- Dadas cláusulas, elas compartilham no máximo variável.
Eu gostaria de saber o quão difícil é contar as tarefas satisfatórias dessa fórmula.
Atualização 06/04/2013 12:55
Eu também gostaria de saber o quão difícil é determinar a paridade do número de tarefas satisfatórias.
Atualização 11/04/2013 22:40
E se, além das restrições descritas acima, também introduzirmos as duas restrições a seguir:
- A fórmula é plana.
- A fórmula é bipartida.
Atualização 16/04/2013 23:00
Cada tarefa satisfatória corresponde a uma cobertura de borda de um gráfico de . Após uma extensa pesquisa, o único artigo relevante que pude encontrar sobre as capas das bordas é o (3) já mencionado na resposta de Yuval. No início desse artigo, os autores dizem "Nós iniciar o estudo de amostragem (e a questão conexa de contar) de todas as tampas beira de um gráfico" . Estou muito surpreso que esse problema tenha recebido tão pouca atenção (em comparação com a contagem de capas de vértices, que é amplamente estudada e muito melhor compreendida, para várias classes de gráficos). Não sabemos se a contagem de capas de arestas é difícil. Não sabemos se a determinação da paridade do número de capas de borda é-hard também.
Atualização 09/06/2013 07:38
A determinação da paridade do número de capas de arestas é -hard, verifique a resposta abaixo.
fonte
Respostas:
Em qualquer gráfico, a paridade do número de capas de vértices é igual à paridade do número de capas de arestas.
Pelo menos a segunda metade da questão foi resolvida.
fonte
Seu problema provavelmente é # P-completo, embora eu não tenha sido capaz de encontrá-lo na literatura.
Outra maneira de indicar seu problema é "# 3-regular-edge-cover". Dada uma fórmula, construa um gráfico no qual cada cláusula corresponda a um vértice e cada variável corresponda a uma aresta. Como a fórmula é 3CNF, o gráfico é 3-regular (ou possui o grau máximo 3, dependendo da definição). Além disso, o gráfico é simples. Uma tarefa satisfatória é igual a uma cobertura de borda.
Aqui estão alguns problemas relacionados:
fonte