Jaka jest złożoność Median-SAT?

Niech będzie formułą CNF z n zmiennymi i klauzulami m . Niech t ∈ { 0 , 1 } n reprezentuje przypisanie zmiennej, a f φ ( t ) ∈ { 0 , … , m } zliczają liczbę klauzul spełnionych przez przypisanie zmiennej do φ . Następnie zdefiniuj Median-SAT jako problem obliczania mediany wartości f φ ( t ) dla wszystkich t ∈ { 0 , $\varphi$$n$$m$$t \in \{ 0,1 \}^n$$f_{\varphi}(t) \in \{ 0, \ldots , m \}$$\varphi$$f_{\varphi}(t)$ . Na przykład, jeśli φ jest tautologią, wówczas rozwiązaniem dla Median-SAT będzie m, ponieważ niezależnie od przypisania każda klauzula będzie spełniona. Jednak w przypadku ¯ S A T rozwiązaniem dla Median-SAT może być gdziekolwiek między 0 a m - 1 .$t \in \{ 0,1 \}^n$$\varphi$$m$$\overline{SAT}$$0$$m-1$

To pytanie powstało, gdy zastanawiałem się nad dwoma naturalnymi rozszerzeniami SAT, MAX-SAT i #SAT i jaka byłaby trudność wynikającego z tego problemu, gdyby zostały one połączone razem. Dla MAX-SAT musimy znaleźć konkretne przypisanie zmiennych, aby zmaksymalizować liczbę zmiennych spełnianych przez . Dla #SAT musimy policzyć, ile przypisań spełnia wszystkie m klauzul φ . Ten wariant kończy się głównie jako rozszerzenie #SAT (a właściwie #WSAT ), ale zachowuje trochę smaku MAX-SAT, ponieważ liczymy liczbę spełnionych klauzul, a nie tylko decydujemy, czy wszyscy są zadowoleni, czy nie.$\varphi$$m$$\varphi$

$\varphi$$\varphi$

Zdaję sobie sprawę, że ten problem jest nieco arbitralny; obliczanie średniej lub liczby trybów klauzul spełnianych przez każde przypisanie zmiennej wydaje się przechwytywać tę samą jakość. Prawdopodobnie robi to również wiele innych problemów.

Czy ten problem został zbadany, być może pod innym pozorem? Jak trudne jest to w porównaniu do #SAT? A priori nie jest dla mnie jasne, że Median-SAT jest nawet zawarty w FPSPACE, chociaż wydaje się, że jest zawarty w FEXPTIME.

$k$$k$$k$$k$

$\#P$$FP^{\#P} \subseteq FPSPACE$

$\lceil \lg m+1 \rceil$

$M(\varphi)$$\varphi$$k$$\psi_k$$x$$x$$k$$\varphi$$\varphi$$k$$\psi_k$

$\psi_k$$\psi_k$$M(\varphi) \ge k$$M(\varphi)$$k=m/2$$k$$\lg m+1$$M(\varphi)$. Każda iteracja wymaga jednego zapytania do naszej wyroczni dla MAJSAT.