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

Niech będzie formułą CNF z zmiennymi i klauzulami . Niech reprezentuje przypisanie zmiennej, a zliczają liczbę klauzul spełnionych przez przypisanie zmiennej do . Następnie zdefiniuj Median-SAT jako problem obliczania mediany wartości wszystkich $\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 ponieważ niezależnie od przypisania każda klauzula będzie spełniona. Jednak w przypadku rozwiązaniem dla Median-SAT może być gdziekolwiek między a . $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 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.

cc.complexity-theory sat counting-complexity

— Huck Bennett
źródło

F P^{# P} \subseteq F P S P A C E

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

k \leq m

$k\leq m$

k

$k$

@Colin uczynić z tego odpowiedź?

— Suresh Venkat,

k \leq m

$k \leq m$

@Tsuyoshi, jaka jest twoja definicja SAT? Czy zezwalamy na powtarzanie klauzul? lub literały i / lub zmienne w danych klauzulach? Ponieważ jeśli nie pozwalasz na powtarzanie literałów i / lub zmiennych w podanych klauzulach, nie możesz mieć formuły CNF, która jest tautologią.

— Tayfun Pay

@Tayfun - faktycznie zadałem to pytanie, Tsuyoshi pomógł przy drobnej edycji. Masz rację co do tautologii w formule CNF, która wymaga powtarzających się literałów. Każdy wariant SAT byłby interesujący, powtarzanie CNF-SAT bez var w klauzulach (w którym to przypadku tautologie są niemożliwe), a może bardziej ogólnie CIRCUIT-SAT. Nie sądzę, aby ten wybór zmienił smak pytania.

— Huck Bennett

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

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

— Colin McQuillan
źródło

Masz całkowitą rację. Jest to bardzo czysty argument, i wydaje mi się, że dość oczywiste z definicji #P. Nauczyłem się czegoś.

— Huck Bennett

k

$k$

# P

$\#P$

# P

$\#P$

F P^{# P}

$FP^{\#P}$

$\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.

— DW
źródło