Modelos SAT vs Exatamente exclusivos

SAT exclusivo é o problema bem conhecido: dada a fórmula CNF , é verdade que tem exatamente um modelo? $F$ $F$

Estou interessado no problema «Exatamente -SAT»: dada uma fórmula CNF e um número inteiro , é verdade que tem exatamente modelos? $m$ $F$ $m>1$ $F$ $m$

Ambos os problemas parecem semelhantes. Então, minhas perguntas são:

1- O polytime «Exatamente -SAT» (muitos-um ou Turing) é redutível ao Unique SAT? $m$

2- Você conhece alguma referência sobre o assunto?

Obrigado por suas respostas.

Adendo , primeiros artigos sobre a complexidade do Exatamente SAT: $m$

1- Janos Simon, Sobre a Diferença Entre Um e Muitos, Nos Anais do Quarto Colóquio sobre Autômatos, Idiomas e Programação, 480-491, 1977.

2- Klaus W. Wagner, A complexidade dos problemas combinatórios com representação sucinta de entradas, Acta Informatica, 23, 325-356, 1986.

Nos dois artigos, Exatamente SAT ( ) é mostrado como completo (com muitas reduções de uma), onde a classe é da Hierarquia de Contagem (CH) das classes de complexidade. Informalmente, contém todos os problemas que podem ser expressos para decidir se uma determinada instância tem pelo menos muitas provas de tamanho polinomial ( sabe-se que a classe coincide com a classe ). A classe é uma variante de , onde "exatamente " substitui "pelo menos ". $m$ $m \geq 1$ $C=$ $C$ $C$ $m$ $C$ $PP$ $C=$ $C$ $m$ $m$

cc.complexity-theory reference-request np-hardness sat reductions Xavier Labouze
fonte

É polytime Turing redutível: encontre uma solução, adicione uma cláusula que a elimine e repita até que a fórmula se torne insatisfatória.

Kaveh

1. a máquina informará o número de soluções ou que possui mais de soluções. 2. você pode adicionar a negação da conjunção que descreve a solução.

m

$m$

Kaveh

Se você não conhece a relação entre o PP e a contagem do número de soluções, consulte um livro sobre teoria da complexidade, como Papadimitriou.

Tsuyoshi Ito

(1) Se m for polinomialmente limitado, seu problema é polinomialmente um número redutível ao Unique SAT, tratando uma lista de m soluções classificadas na ordem lexicográfica como um único certificado. (2) Por favor, não tome minha resposta como prova de que você fez sua pergunta no lugar certo. Penso que esta questão em particular está na linha de fronteira entre no tópico e fora do tópico. Você realmente deve considerar fazer suas perguntas futuras em outro lugar.

Tsuyoshi Ito

Embora você declare que m é polinomialmente limitado, algumas das declarações na pergunta exigem que m seja arbitrário e não seja mais válido se você restringir m para ser polinomialmente limitado. Você precisa entender do que está falando antes de poder fazer uma pergunta coerente. É por isso que não quero postar uma resposta para esta pergunta aqui, onde as perguntas devem estar no nível da pesquisa.

Tsuyoshi Ito

Para geral , exatamente m-sat é estritamente mais difícil que u-sat (portanto, não se reduz a ele) a menos que o PH entre em colapso. A razão é que o PP pode ser obtido usando um quantificador existencial em consultas exatamente m-SAT (existe m> (metade das atribuições), de modo que exatamente m-SAT), portanto, se exatamente m-sat está no k ' No nível de PH, o PP está no nível (k + 1) e a hierarquia entra em colapso (uma vez que P ^ PP contém PH). Mas u-sat está claramente no segundo nível de PH (na verdade, em uma subclasse chamada DP). $m$

Por outro lado, como @Tsuyoshi mencionado acima, se é polinomial, então exatamente m-sat é muitos um reudível para u-sat. $m$

Noam
fonte

m

$m$

n

$n$

m

$m$

m

$m$

m = 2^{O (n)}

$m= 2^{O(n)}$

m

$m$

m

$m$

M grande ainda não coloca o problema em P. A publicação de atualização está incorreta, pois a afirmação de que exatamente-k-sat é C = P-complete é verdadeira quando k faz parte da entrada e, portanto, sua redução para k / 2 -sat não faz sentido.

Noam

m

$m$

m

$m$

y_{1}, y_{2} \dots y_{m}

$y_1,y_2 \cdots y_m$

F^{'} = F \land y_{1} \land y_{2} \land \dots \land y_{m}

$F'=F\land y_1 \land y_2 \land \cdots \land y_m$

F^{'}

$F'$

F

$F$

m

$m$

F^{'}

$F'$

F^{'}

$F'$

F^{'}

$F'$

F

$F$

m

$m$

| F |

$|F|$

Modelos SAT vs Exatamente exclusivos

Respostas: