Untere Schranken für #SAT?

Das Problem #SAT ist das kanonische # P-vollständige Problem. Es ist eher ein Funktionsproblem als ein Entscheidungsproblem. Sie fragt mit einer Booleschen Formel in der Aussagenlogik, wie viele befriedigende Zuordnungen hat. Welches sind die besten Untergrenzen für #SAT?$F$$F$

Meines Wissens hat niemand herausgefunden, wie man die "Zähllösungen" -Eigenschaft von #SAT in irgendeiner Untergrenze für deterministische Algorithmen ausnutzt. Leider sind die bekanntesten Untergrenzen für #SAT im Grunde die gleichen wie für SAT.

Es wurden jedoch einige Fortschritte erzielt. Beachten Sie, dass die Entscheidungsversion von #SAT wird „Majority-SAT“ genannt: gegeben eine Formel, tun mindestens der möglichen Zuordnungen es erfüllen? $1/2$"Majority-SAT" ist -vollständig, und wenn ein Algorithmus für Majority-SAT gegeben ist, kann man #SAT mit O ( n ) -Aufrufen an den Algorithmus lösen .$PP$$O(n)$

Das, was die Menschen am nächsten an neue Untergrenzen für #SAT geraten sind (von denen nicht bekannt ist, dass sie für SAT gelten), ist mit Untergrenzen für "Mehrheit-der-Mehrheit-SAT": eine Satzformel über zwei Mengen von Variablen X und Y gegeben zumindest für die der möglichen Zuordnungen auf X , ist es wahr , dass mindestens 1 / 2 die Zuweisungen zu Y die Formel erfüllbar machen? $1/2$$X$$1/2$$Y$Dieses Problem liegt in der "zweiten Ebene" der Zählhierarchie (der Klasse ). Quanten-Zeit-Raum-Untergrenzen (und mehr) sind für diese Klasse bekannt.$PP^{PP}$

Die Umfrage unter http://pages.cs.wisc.edu/~dieter/Papers/sat-lb-survey-fttcs.pdf gibt einen Überblick über die Ergebnisse in dieser Richtung.

$NP=RP$