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 F ma. Jakie są najlepsze dolne granice na #SAT?$F$$F$

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.

$NP=RP$