Limites inferiores em #SAT?

14

O problema #SAT é o problema canônico # P-complete. É um problema de função e não de decisão. Ele pergunta, dada uma fórmula booleana na lógica proposicional, quantas atribuições satisfatórias F possui. Quais são os melhores limites inferiores no #SAT?FF

Giorgio Camerani
fonte

Respostas:

26

Que eu saiba, ninguém descobriu como explorar a propriedade "soluções de contagem" do #SAT em qualquer limite inferior nos algoritmos determinísticos, portanto, infelizmente, os limites inferiores mais conhecidos para o #SAT são basicamente os mesmos que para o SAT.

No entanto, houve um pequeno progresso. Note-se que a versão decisão do #SAT é chamado de "Maioria-SAT": dada uma fórmula, fazer pelo menos do possível atribuições satisfazê-lo? 1/2"Maioria-SAT" é -completo, e tendo em conta um algoritmo para a maioria-sab, pode-se resolver #SAT com S ( n ) as chamadas para o algoritmo.PPO(n)

O mais próximo que as pessoas chegaram de novos limites inferiores para o #SAT (que não são conhecidos por manter o SAT) é o limite mais baixo para o "Majority-of-Majority-SAT": dada uma fórmula proposicional sobre dois conjuntos de variáveis ​​X e Y , para, pelo menos, dos possíveis atribuições para X , é verdade que, pelo menos, 1 / 2 das atribuições para Y fazer a fórmula satisfatível? 1/2X1/2YEsse problema está no "segundo nível" da hierarquia de contagem (a classe ). Os limites inferiores do tempo-espaço quântico (e mais) são conhecidos para esta classe.PPPP

A pesquisa em http://pages.cs.wisc.edu/~dieter/Papers/sat-lb-survey-fttcs.pdf fornece uma visão geral dos resultados nessa direção.

Ryan Williams
fonte
Obrigado pela sua resposta útil. Obrigado também pelo ponteiro para a pesquisa.
Giorgio Camerani
6

Além disso, não tem #SAT esquema totalmente polinomial randomizado aproximação (FPRAS) a menos que .NP=RP

Mohammad Al-Turkistany
fonte
1
Você poderia fornecer uma referência?
MS Dousti 9/09/10
2
Intuitivamente, um FRPAS permitirá distinguir o caso de soluções zero e soluções diferentes de zero, que é o problema NP-complete SAT.
Robin Kothari
@SadeqDousti A referência é David Zuckerman, Em versões não aproximadas de problemas NP-completos , SIAM Journal on Computing 25 (6): 1293-1304, 1996. Links: DOI , página inicial do autor . De fato, ele prova o resultado mais forte de que você não pode nem se aproximar do logaritmo do número de soluções, a menos que NP = RP.
David Richerby
@DavidRicherby: Eu não esperava uma resposta depois de três anos! Muito obrigado: D
MS Dousti