Какова сложность Median-SAT?

Пусть - формула CNF с n переменными и m предложениями. Пусть t ∈ { 0 , 1 } n представляет присваивание переменной, а f φ ( t ) ∈ { 0 , … , m } подсчитывает количество предложений, удовлетворяемых присваиванием переменной φ . Затем определите Median-SAT как задачу вычисления медианного значения f φ ( t ) по всем t ∈ { 0 , $\varphi$$n$$m$$t \in \{ 0,1 \}^n$$f_{\varphi}(t) \in \{ 0, \ldots , m \}$$\varphi$$f_{\varphi}(t)$ . Например, если$t \in \{ 0,1 \}^n$$\varphi$ является тавтологией, то решение Median-SAT будет равно поскольку независимо от назначения каждое условие будет выполнено. Однако в случае ¯ S A T решение Median-SAT может быть где -то между 0 и т - 1 .$m$$\overline{SAT}$$0$$m-1$

Этот вопрос возник, когда я размышлял над двумя естественными расширениями SAT, MAX-SAT и #SAT, и какова будет сложность возникшей проблемы, если их объединить. Для MAX-SAT мы должны найти конкретное присвоение переменной, чтобы максимизировать число переменных, удовлетворяемых . Для #SAT мы должны посчитать, сколько заданий удовлетворяют всем$\varphi$ предложениям φ . Этот вариант сводится в основном как расширение #SAT (и фактически#WSAT), но сохраняет некоторуюразновидностьMAX-SAT в том, что мы подсчитываем количество удовлетворенных предложений, а не просто решаем, все ли они удовлетворены или не.$m$$\varphi$

Эта проблема кажется сложнее, чем #SAT или #WSAT. Для каждого присваивания переменной #SAT решает булеву задачу о том, удовлетворяет ли это присваивание или нет, тогда как Median-SAT определяет, «в какой степени»удовлетворяется φ с точки зрения количества предложений, которым удовлетворяет присвоение.$\varphi$$\varphi$

Я понимаю, что эта проблема несколько произвольна; вычисление среднего или модового числа предложений, удовлетворяемых каждым присвоением переменной, похоже, отражает то же качество. Вероятно, многие другие проблемы тоже.

Была ли эта проблема изучена, возможно, под другим видом? Насколько это сложно по сравнению с #SAT? Мне априори не ясно, что Median-SAT даже содержится в FPSPACE, хотя кажется, что он содержится в FEXPTIME.

Учитывая экземпляр SAT, целое число и присвоение переменной, мы можем за полиномиальное время решить , удовлетворяются ли ровно k предложений, просто посчитав количество удовлетворенных предложений и проверив, равно ли это число k . Следовательно, мы можем вычислить общее количество переменных, удовлетворяющих точно k предложениям, используя$k$$k$$k$$k$ оракула #P .

Как и Max-SAT, Median-SAT можно вычислить за полиномиальное время с помощью оракула Это показывает , что проблема заключается в Р Р # Р ⊆ F P S P A C E .$\#P$$FP^{\#P} \subseteq FPSPACE$

$\lceil \lg m+1 \rceil$ вызовов оракула для MAJSAT.

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

$\psi_k$$\psi_k$$M(\varphi) \ge k$. So, to learn $M(\varphi)$, apply binary search (start with $k=m/2$, then increase or decrease $k$ according to the results from the oracle). After $\lg m+1$ iterations, the binary search reveals the value of $M(\varphi)$. Each iteration requires one query to our oracle for MAJSAT.