Untere Schranken für #SAT?

14

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?FF

Giorgio Camerani
quelle

Antworten:

26

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 .PPO(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/2X1/2YDieses Problem liegt in der "zweiten Ebene" der Zählhierarchie (der Klasse ). Quanten-Zeit-Raum-Untergrenzen (und mehr) sind für diese Klasse bekannt.PPPP

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

Ryan Williams
quelle
Vielen Dank für Ihre hilfreiche Antwort. Danke auch für den Hinweis auf die Umfrage.
Giorgio Camerani
6

NP=RP

Mohammad Al-Turkistany
quelle
1
Könnten Sie eine Referenz angeben?
MS Dousti,
2
Mit einem FRPAS können Sie intuitiv den Fall von Nulllösungen und Nicht-Nulllösungen unterscheiden, bei dem es sich um das NP-vollständige Problem SAT handelt.
Robin Kothari
@SadeqDousti Die Referenz ist David Zuckerman, Über nicht annehmbare Versionen von NP-vollständigen Problemen , SIAM Journal on Computing 25 (6): 1293-1304, 1996. Links: DOI , Homepage des Autors . Tatsächlich beweist er das stärkere Ergebnis, dass man den Logarithmus der Anzahl der Lösungen nur annähern kann, wenn NP = RP.
David Richerby
@DavidRicherby: Ich habe nicht erwartet, nach 3 Jahren eine Antwort zu bekommen! Vielen Dank: D
MS Dousti