# Gradual increase in hardness from P to PH of #SAT

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.

• If it helps, this question is related to cstheory.stackexchange.com/questions/20490/… . – Pavithran Iyer Jan 8 '14 at 15:02
• It can't be complete unless $\Sigma_{k-1}^P$ is closed under complement, which would imply that the polynomial hierarchy collapses. – Peter Shor Jan 8 '14 at 19:29
• 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 Jan 8 '14 at 21:05