Contando redução de #SAT para #HornSAT?

8

É possível encontrar uma redução na contagem de #SAT para #HornSAT? Eu não encontrei esta pergunta postada aqui, então decidi verificar se alguém tem alguma resposta para isso. Deixe-me explicar o que quero dizer com contagem de redução.

Suponha que são dois problemas de contagem. Por exemplo, #SAT pergunta como muitas atribuições satisfatível estão lá para uma instância específica φ , e f , g são problemas de contagem semelhantes encontrando número total de testemunhas. Uma redução fracamente parcimoniosa da contagem de f para g consiste em um par de funções computáveis ​​no tempo polinomial σ : { 0 , 1 } { 0 , 1 }f,g:{0,1}Nϕf,gfg E τ : { 0 , 1 } * × NN tal que f ( x ) = τ ( x , g ( σ ( x ) ) ) . No caso em que f ( x ) = g ( σ ( x ) ) , isso é conhecido como redução de contagem fortemente parcimoniosa.σ:{0,1}{0,1}τ:{0,1}×NNf(x)=τ(x,g(σ(x)))f(x)=g(σ(x))

Percebo que, se houver uma redução de contagem de #SAT para #HornSAT, deve ser uma redução parcimoniosa: uma forte redução implicaria que as instâncias #SAT e #HornSAT terão um número zero ou diferente de zero de soluções juntas, e assumindo que , isto é impossível (como HORNSAT P enquanto SAT é N P -completo).PNPPNP

Então, minha pergunta é: há alguma redução de parcimônia parcimoniosa de #SAT para #HornSAT? Nesse caso, alguém pode me dar alguma referência?

David
fonte
2
“#HornSAT está # P-completo” significa que todo problema de P pode ser reduzido para #HornSAT por uma redução contada (fracamente parcimoniosa).
Tsuyoshi Ito
1
O que significa fracamente vs. fortemente parcimonioso?
Huck Bennett
@ Huck Bennett ... Eu mencionei a definição matemática na pergunta. Informalmente, podemos dizer que uma forte redução significa que ambos os problemas têm o mesmo número de soluções. Redução fraca significa que o número de soluções da instância original do problema pode ser encontrado em tempo polinomial a partir do número de soluções da instância reduzida do problema.
David
@TsuyoshiIto .. certo, significa que deve haver uma redução na contagem (pouco parcimoniosa) de #SAT para #HornSAT. Eu quero saber essa redução. Não encontrei nenhuma redução direta ou indireta. Basicamente, não sei como provar "#HornSAT é # P-completo". Pode ser que eu não sou tão bom na pesquisa do google. Alguma referência ??
David

Respostas:

10

ϕψ

Radu Curticapean
fonte
1
Muito obrigado pelo ponteiro. Isso realmente me ajuda muito. :)
David