4
$\begingroup$

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.

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

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.