É 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 } E τ : { 0 , 1 } * × N → N tal que f ( x ) = τ ( x , g ( σ ( x ) ) ) . No caso em que f ( x ) = g ( σ ( x ) ) , isso é conhecido como redução de contagem fortemente parcimoniosa.
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).
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?
Respostas:
fonte