Dolna granica na #SAT?

Problem #SAT jest kanonicznym problemem # P-zupełnym. Jest to raczej problem funkcji niż problem decyzyjny. Pyta, biorąc pod uwagę wartość logiczną formuła w rachunku zdań, ilu spełniających zadania ma. Jakie są najlepsze dolne granice na #SAT? $F$ $F$

— Giorgio Camerani
źródło

Odpowiedzi:

O ile mi wiadomo, nikt nie wymyślił, jak wykorzystać właściwość #SAT „rozwiązań zliczających” w jakiejkolwiek dolnej granicy algorytmów deterministycznych, więc niestety najlepiej znane dolne granice dla #SAT są zasadniczo takie same jak dla SAT.

$1/2$ $PP$ $O(n)$

$1/2$ $X$ $1/2$ $Y$ $PP^{PP}$

Ankieta pod adresem http://pages.cs.wisc.edu/~dieter/Papers/sat-lb-survey-fttcs.pdf zawiera przegląd wyników w tym kierunku.

— Ryan Williams
źródło

Dziękuję za przydatną odpowiedź. Dziękuję również za wskaźnik do ankiety.

— Giorgio Camerani,

$NP=RP$

— Mohammad Al-Turkistany
źródło

Czy możesz podać referencje?

— MS Dousti,

Intuicyjnie FRPAS pozwoli ci rozróżnić przypadki rozwiązań zerowych i niezerowych, co jest problemem NP-zupełnym SAT.

— Robin Kothari,

@SadeqDousti Odniesieniem jest David Zuckerman, O niedopuszczalnych wersjach problemów NP-zupełnych , SIAM Journal on Computing 25 (6): 1293-1304, 1996. Linki: DOI , strona główna autora . W rzeczywistości dowodzi on silniejszego wyniku, że nie można nawet zbliżyć logarytmu liczby rozwiązań, chyba że NP = RP.

— David Richerby

@DavidRicherby: Nie spodziewałem się odpowiedzi po 3 latach!

— Wielkie