2
$\begingroup$

Given
$$\mathrm{\#3SAT} = \{ (w, y) \mid w\text{ is a $\mathrm{3SAT}$ instance with at least $y$ satisfying assignments}\}\,,$$ prove that $\mathrm{\#3SAT}$ is NP-Hard.

I am currently stuck with this one.

Basically $\mathrm{\#3SAT}$ is the counting version of $\mathrm{3SAT}$ and to me it is seems clear that establishing membership in the language is more complex than establish the classic $\mathrm{3SAT}$ membership.

I'm trying to reason through the prover-verifier paradigm: let's say you have a $\mathrm{3SAT}$ instance, now suppose the certificate for that instance is $n$ bits. It is obvious that the certificate for the same instance but translated into $\mathrm{\#3SAT}$ with let's say $y=10$ would be at least $10n$ bits. So if the first can be examined in time $t$ then the second will take at least $10t$ and so on. However I am not satisfied with this reasoning, it seems incomplete and superficial. I would greatly appreciate your advice on how to proceed with this proof. Thanks in advance.

|cite|improve this question
$\endgroup$
3
$\begingroup$

It seems that you're trying to prove that $\#\mathrm{3SAT}$ is in $\mathrm{NP}$. Since $\#\mathrm{3SAT}$ is $\mathrm{\#P}$-complete, and $\mathrm{\#P}$ seems to be harder than anything in the polynomial hierarchy, it's very unlikely that $\#\mathrm{3SAT}\in\mathrm{NP}$.

The error in your attempted proof is that your certificate doesn't have polynomial length. A satisfying assignment has length $\Theta(|x|)$ (the formula can't have more variables than its length, but it could be of the form $(x_1\lor x_2\lor x_3) \land (x_4\lor x_5\lor x_6) \land\dots$). The number $y$ could have any value between zero and $2^{|y|}-1$, so your certificate has length about $|x|2^{|y|}$, which is exponential in the input size.

However, the question asks you to prove that it's $\mathrm{NP}$-hard, not that it's $\mathrm{NP}$-complete. You just need to prove that there's a polynomial-time reduction from some $\mathrm{NP}$-complete problem to $\#\mathrm{3SAT}$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ thanks for the answer. What about this sketch: a NTM can decide membership to 3SAT in polynomial time. Then to decide membership in #3SAT it will take a polynomial expansion on the time implied to decide 3SAT. $\endgroup$ – Yamar69 Jun 17 '19 at 10:02
  • $\begingroup$ @Yamar69 You're supposed to be reducing problems to $\mathrm{\#3SAT}$, not designing algorithms for $\mathrm{\#3SAT}$. $\endgroup$ – David Richerby Jun 17 '19 at 10:07
  • $\begingroup$ David Richerby i know but that is the hard part for me :( can you give me a direction? $\endgroup$ – Yamar69 Jun 17 '19 at 10:11
  • 1
    $\begingroup$ Not being rude, but I'm not sure you do know. You started off trying to prove $\mathrm{\#3SAT}\in\mathrm{NP}$. I said don't do that; reduce an $\mathrm{NP}$-complete problem to it. Then you tried to produce an algorithm for $\mathrm{\#3SAT}$ and I said don't do that; reduce an $\mathrm{NP}$-complete problem to it. It doesn't seem to me that you've spent any time trying to actually reduce an $\mathrm{NP}$-complete problem to $\mathrm{\#3SAT}$. It's only eight minutes since I last told you to do that and you showed no evidence of having tried to do it before then. $\endgroup$ – David Richerby Jun 17 '19 at 10:17
  • $\begingroup$ One last question, I noticed that you have edited your answer by adding a comment on the length of the certificate. I understand what you wrote but it seems to me that it is correct only if you take into consideration the space of all possible certificates. Basically what I was saying was this: if you have an instance of # 3SAT with y = 10, The certificate that must be given as a meal to the verifier must contain only 10 different distributions of variables that make the input belonging to # 3SAT(10) and therefore it will be only 10 times larger than the 3SAT's one. $\endgroup$ – Yamar69 Jun 17 '19 at 10:36
2
$\begingroup$

The subset for $y = 1$ is 3SAT, which is NP-complete (thus NP-hard); the full set can't be easier...

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.