<p>This problem can be solved using $\lceil \lg m+1 \rceil$ invocations of an oracle for MAJSAT.</p>

<p>Let $M(\varphi)$ denote the desired median value for $\varphi$.  For fixed $k$, define the formula $\psi_k$ so it is true for assignment $x$ iff $x$ satisfies at least $k$ of the clauses of $\varphi$.  Notice that given $\varphi$ in CNF form and given $k$, you can easily construct $\psi_k$ in CNF form in polynomial time.</p>

<p>Now suppose we had an oracle for MAJSAT.  Querying it on the formula $\psi_k$ would tell us whether the majority of assignments make the formula $\psi_k$ true, or equivalently, whether $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. </p>

CC BY-SA 3.0
2013-09-04T01:00:00.947Z
2013-09-04T01:00:00.947Z
D.W.
<p>Given an instance of SAT, an integer $k$, and a variable assignment, we can decide in polynomial time whether exactly $k$ clauses are satisfied, simply by counting the number of clauses that are satisfied and testing whether that number equals $k$. Hence we can calculate the total number of variable assigments satisfying exactly $k$ clauses using a <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aSymbols#sharpp">#P oracle</a>.</p>

<p>So like Max-SAT, Median-SAT can be computed in polynomial time using a $\#P$ oracle. This shows that the problem is in $FP^{\#P} \subseteq FPSPACE$.</p>

CC BY-SA 2.5
2011-02-17T02:45:12.143Z
You're absolutely right. This is a very clean argument, and I guess pretty obvious from the definition of #P. I learned something.
Huck Bennett
CC BY-SA 2.5
2011-02-19T05:25:47.633Z
Let me elaborate on this a little more: Colin's saying that because we can determine in polynomial time whether a particular variable assignment satisfies $k$ clauses that we can nondeterministically guess a variable assignment and then count how many accepting paths (i.e. accepting variable assignments) this query had using the $\#P$ oracle (by definition of $\#P$). By iterating through k=1 to m, we can count the median number of clauses satisfied in $FP^{\#P}$.
Huck Bennett
CC BY-SA 2.5
2011-02-16T18:15:45.250Z
2011-02-16T18:15:45.250Z
Colin McQuillan
<p>Let $\varphi$ be a CNF formula with $n$ variables and $m$ clauses. Let $t \in \{ 0,1 \}^n$  represent a variable assignment and $f_{\varphi}(t) \in \{ 0, \ldots , m \}$ count the number of clauses satisfied by a variable assignment to $\varphi$. Then define Median-SAT as the problem of computing the median value of $f_{\varphi}(t)$ over all $t \in \{ 0,1 \}^n$.  For example, if $\varphi$ is a tautology then the solution to Median-SAT will be $m$ since regardless of assignment every clause will be satisfied. However in the case of $\overline{SAT}$ the solution to Median-SAT could be anywhere between $0$ and $m-1$.</p>

<p>This question arose when I was pondering two natural extensions of SAT, MAX-SAT and #SAT, and what the difficulty of the resulting problem would be if they were put together. For MAX-SAT we have to find a particular variable assignment to maximize the number of variables satisfied by $\varphi$. For #SAT we have to count how many assignments satisfy all $m$ clauses of $\varphi$. This variant winds up mainly as an extension of #SAT (and in fact of <a href="http://qwiki.stanford.edu/index.php/Complexity_Garden#sharpwsat">#WSAT</a>), but retains some of the flavor of MAX-SAT in that we count the number of satisfied clauses rather than just deciding whether they're all satisfied or not.</p>

<p>This problem seems harder than #SAT or #WSAT. For each variable assignment #SAT decides the Boolean problem of whether that assignment satisfies $\varphi$ or not whereas Median-SAT determines "to what extent" $\varphi$ is satisfied in terms of the number of clauses that an assignment satisfies.</p>

<p>I realize that this problem is somewhat arbitrary; computing the average or mode number of clauses satisfied by each variable assignment seems to capture the same quality. Probably many other problems do too.</p>

<p>Has this problem been studied, perhaps under a different guise? How hard is it compared to #SAT? It's not clear to me a priori that Median-SAT is even contained in FPSPACE, although it does seem to be contained in FEXPTIME.</p>

CC BY-SA 2.5
2011-02-07T11:31:06.150Z
It's in $FP^{\#P}\subseteq FPSPACE$: for each $k\leq m$ we can count the number of assignments satisfying at least $k$ clauses using a #P oracle.
Colin McQuillan
CC BY-SA 2.5
2011-02-07T19:29:12.763Z
@Colin make this into an answer ?
Suresh Venkat
CC BY-SA 2.5
2011-02-07T19:37:56.063Z
Yes, this would make a good answer. Could you elaborate on how to query the #P oracle to check whether $k \leq m $ clauses are satisfied? I couldn't figure out how to do it efficiently.
Huck Bennett
CC BY-SA 2.5
2011-02-11T13:35:14.083Z
@Tsuyoshi, what is your definition of SAT? Are we allowing repetition of clauses? or literals and/or variables in a given clauses? Because if you do not allow repetition of literals and/or variables in a given clauses you cannot have a CNF formula that is a tautology..
Tayfun Pay
CC BY-SA 2.5
2011-02-11T15:23:21.267Z
@Tayfun - I actually asked this question, Tsuyoshi helped with a minor edit. You're right about a tautology in a CNF formula requiring repeated literals. Any SAT variant would be interesting, CNF-SAT w/o var repetition in clauses (in which case tautologies are impossible), or maybe CIRCUIT-SAT more generally. I don't think this choice changes the flavor of the question.
Huck Bennett
CC BY-SA 2.5
2011-02-16T18:55:34.223Z
@Huck: Do you care about approximations? If so, you can surely approximate the value in polynomial time (i.e. in FP) by sampling.
Joe Fitzsimons
CC BY-SA 2.5
2011-02-17T01:57:15.590Z
@Joe: Good point, but of course there will be high variance in the sampling estimates.
Huck Bennett
CC BY-SA 2.5
2011-02-17T11:15:42.363Z
@Huck: the variance shouldn't be high, since each t satisfies between 0 and m clauses, so the difference made by the extremely rare cases will be very small.
Joe Fitzsimons
CC BY-SA 2.5
2011-02-19T05:11:51.253Z
@Joe: You're right. It'd be interesting to look into this further.
Huck Bennett
<cc.complexity-theory><sat><counting-complexity>
What's the complexity of Median-SAT?
Huck Bennett
# What's the complexity of Median-SAT?

(Asked by: username_0 on 2011-02-07)

Let $\varphi$ be a CNF formula with $n$ variables and $m$ clauses. Let $t \in \{ 0,1 \}^n$ represent a variable assignment and $f\_{\varphi}(t) \in \{ 0, \ldots , m \}$ count the number of clauses satisfied by a variable assignment to $\varphi$. Then define Median-SAT as the problem of computing the median value of $f\_{\varphi}(t)$ over all $t \in \{ 0,1 \}^n$. For example, if $\varphi$ is a tautology then the solution to Median-SAT will be $m$ since regardless of assignment every clause will be satisfied. However in the case of $\overline{SAT}$ the solution to Median-SAT could be anywhere between $0$ and $m-1$.

This question arose when I was pondering two natural extensions of SAT, MAX-SAT and #SAT, and what the difficulty of the resulting problem would be if they were put together. For MAX-SAT we have to find a particular variable assignment to maximize the number of variables satisfied by $\varphi$. For #SAT we have to count how many assignments satisfy all $m$ clauses of $\varphi$. This variant winds up mainly as an extension of #SAT (and in fact of [#WSAT](http://qwiki.stanford.edu/index.php/Complexity_Garden#sharpwsat)), but retains some of the flavor of MAX-SAT in that we count the number of satisfied clauses rather than just deciding whether they're all satisfied or not.

This problem seems harder than #SAT or #WSAT. For each variable assignment #SAT decides the Boolean problem of whether that assignment satisfies $\varphi$ or not whereas Median-SAT determines "to what extent" $\varphi$ is satisfied in terms of the number of clauses that an assignment satisfies.

I realize that this problem is somewhat arbitrary; computing the average or mode number of clauses satisfied by each variable assignment seems to capture the same quality. Probably many other problems do too.

Has this problem been studied, perhaps under a different guise? How hard is it compared to #SAT? It's not clear to me a priori that Median-SAT is even contained in FPSPACE, although it does seem to be contained in FEXPTIME.

**Tags:** cc.complexity-theory, sat, counting-complexity

> **Comments:**
> **username_1**: It's in $FP^{\#P}\subseteq FPSPACE$: for each $k\leq m$ we can count the number of assignments satisfying at least $k$ clauses using a #P oracle.  
> **username_2**: @Colin make this into an answer ?  
> **username_0**: Yes, this would make a good answer. Could you elaborate on how to query the #P oracle to check whether $k \leq m $ clauses are satisfied? I couldn't figure out how to do it efficiently.  
> **username_3**: @Tsuyoshi, what is your definition of SAT? Are we allowing repetition of clauses? or literals and/or variables in a given clauses? Because if you do not allow repetition of literals and/or variables in a given clauses you cannot have a CNF formula that is a tautology..  
> **username_0**: @Tayfun - I actually asked this question, Tsuyoshi helped with a minor edit. You're right about a tautology in a CNF formula requiring repeated literals. Any SAT variant would be interesting, CNF-SAT w/o var repetition in clauses (in which case tautologies are impossible), or maybe CIRCUIT-SAT more generally. I don't think this choice changes the flavor of the question.  
> **username_4**: @Huck: Do you care about approximations? If so, you can surely approximate the value in polynomial time (i.e. in FP) by sampling.  
> **username_0**: @Joe: Good point, but of course there will be high variance in the sampling estimates.  
> **username_4**: @Huck: the variance shouldn't be high, since each t satisfies between 0 and m clauses, so the difference made by the extremely rare cases will be very small.  
> **username_0**: @Joe: You're right. It'd be interesting to look into this further.  

---

## 2 answers

### Answer by username_1 on 2011-02-16. Score: 13 | Accepted answer

Given an instance of SAT, an integer $k$, and a variable assignment, we can decide in polynomial time whether exactly $k$ clauses are satisfied, simply by counting the number of clauses that are satisfied and testing whether that number equals $k$. Hence we can calculate the total number of variable assigments satisfying exactly $k$ clauses using a [#P oracle](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aSymbols#sharpp).

So like Max-SAT, Median-SAT can be computed in polynomial time using a $\#P$ oracle. This shows that the problem is in $FP^{\#P} \subseteq FPSPACE$.

> **Comments:**
> **username_0**: You're absolutely right. This is a very clean argument, and I guess pretty obvious from the definition of #P. I learned something.  
> **username_0**: Let me elaborate on this a little more: Colin's saying that because we can determine in polynomial time whether a particular variable assignment satisfies $k$ clauses that we can nondeterministically guess a variable assignment and then count how many accepting paths (i.e. accepting variable assignments) this query had using the $\#P$ oracle (by definition of $\#P$). By iterating through k=1 to m, we can count the median number of clauses satisfied in $FP^{\#P}$.  

---

### Answer by username_5 on 2013-09-04. Score: 3

This problem can be solved using $\lceil \lg m+1 \rceil$ invocations of an oracle for MAJSAT.

Let $M(\varphi)$ denote the desired median value for $\varphi$. For fixed $k$, define the formula $\psi\_k$ so it is true for assignment $x$ iff $x$ satisfies at least $k$ of the clauses of $\varphi$. Notice that given $\varphi$ in CNF form and given $k$, you can easily construct $\psi\_k$ in CNF form in polynomial time.

Now suppose we had an oracle for MAJSAT. Querying it on the formula $\psi\_k$ would tell us whether the majority of assignments make the formula $\psi\_k$ true, or equivalently, whether $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.


---

