<p>We know that counting the number of solutions to $3-SAT$ is the canonical $\#P-Complete$ problem. Equivalently, it is the canonical $PH-Hard$ problem.</p>

<p>However, counting the number of solutions to $3-SAT$ that have weight at most $\log_2n$ (that is, have at most $\log_2n$ variables assigned to <strong>True</strong>) is a problem in $P$.</p>

<p>If we want to look at the complexity of counting solutions to $3-SAT$ with the maximum weight of an assignment, say $w$, as a parameter, it seems that:</p>

<ol>
<li><p>$w = \mathcal{O}(\log_2 n):$ the complexity is $P$</p></li>
<li><p>$w = \mathcal{O}(n):$ Complexity is $PH-Hard$</p></li>
</ol>

<p>It seems fair to tell that:</p>

<blockquote>
  <p>$w = \mathcal{O}(\log_2^kn):$ the complexity of counting solutions to $3-SAT$ is complete (or maybe just hard) for $\Sigma^P_{k-1}$.</p>
</blockquote>

<p>where $\Sigma^P_{k-1}$ is the $k-1$ level of the polynomial hierarchy.</p>

<p>Can anyone please help me see why the above should be true, or otherwise ? Any reference would also greatly help.</p>

CC BY-SA 3.0
2014-01-08T15:02:01.190Z
If it helps, this question is related to http://cstheory.stackexchange.com/questions/20490/weight-enumerator-and-levels-of-polynomial-hierarchy?rq=1 .
Pavithran Iyer
CC BY-SA 3.0
2014-01-08T19:29:04.680Z
It can't be complete unless $\Sigma_{k-1}^P$ is closed under complement, which would imply that the polynomial hierarchy collapses.
Peter Shor 
CC BY-SA 3.0
2014-01-08T21:05:16.610Z
True. About the hardness: take $k=2$. Is it possible to count the number of satisfying assignments of weight $\mathcal{O}(\log_2^2n)$, in polynomial time, with access to an $NP-$oracle ?
Pavithran Iyer
<reference-request><sat><counting-complexity><polynomial-hierarchy>
Gradual increase in hardness from P to PH of #SAT
Pavithran Iyer
# Gradual increase in hardness from P to PH of #SAT

(Asked by: username_0 on 2014-01-08)

We know that counting the number of solutions to $3-SAT$ is the canonical $\#P-Complete$ problem. Equivalently, it is the canonical $PH-Hard$ problem.

However, counting the number of solutions to $3-SAT$ that have weight at most $\log\_2n$ (that is, have at most $\log\_2n$ variables assigned to **True**) is a problem in $P$.

If we want to look at the complexity of counting solutions to $3-SAT$ with the maximum weight of an assignment, say $w$, as a parameter, it seems that:

1. $w = \mathcal{O}(\log\_2 n):$ the complexity is $P$
2. $w = \mathcal{O}(n):$ Complexity is $PH-Hard$

It seems fair to tell that:

> $w = \mathcal{O}(\log\_2^kn):$ the complexity of counting solutions to $3-SAT$ is complete (or maybe just hard) for $\Sigma^P\_{k-1}$.

where $\Sigma^P\_{k-1}$ is the $k-1$ level of the polynomial hierarchy.

Can anyone please help me see why the above should be true, or otherwise ? Any reference would also greatly help.

**Tags:** reference-request, sat, counting-complexity, polynomial-hierarchy

> **Comments:**
> **username_0**: If it helps, this question is related to http://cstheory.stackexchange.com/questions/20490/weight-enumerator-and-levels-of-polynomial-hierarchy?rq=1 .  
> **username_1**: It can't be complete unless $\Sigma_{k-1}^P$ is closed under complement, which would imply that the polynomial hierarchy collapses.  
> **username_0**: True. About the hardness: take $k=2$. Is it possible to count the number of satisfying assignments of weight $\mathcal{O}(\log_2^2n)$, in polynomial time, with access to an $NP-$oracle ?  

---

## 0 answers

