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
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
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
Além disso, não tem #SAT esquema totalmente polinomial randomizado aproximação (FPRAS) a menos que .NP= R P
fonte