1
$\begingroup$

I have a method to solve the $\mathsf{\#P}$ version of 3SAT in a way that seemingly reduces it to an $\mathsf{NP}$ problem. - I don't have a formal understanding of these terms so I will just show an example here.

How many solutions does $\phi=\left(x_1 \vee x_2 \right) \wedge \left(\neg x_1 \vee x_3 \right) \wedge \left(\neg x_2 \vee \neg x_3 \right)$ have?

First convert to a boolean polynomial: $$\phi=\left(x_1 + x_2 -x_1x_2\right) \left(1-x_1+x_1x_3\right) \left(1-x_2x_3 \right)$$

Expand and simplify (using, e.g., $x^2=x$ for Boolean values): $$\phi = x_2 - x_1x_2 + x_1x_3 - x_2x_3$$

Substitute $x_1 = x_2 = x_3 = \frac{1}{2}$ and multiply by $2^n$ where $n$ is the number of variables: $$|\phi| = 2^n\left(\frac{1}{2} - \frac{1}{4} + \frac{1}{4} - \frac{1}{4}\right) = 2^3\frac{1}{4} = 2$$

where $|\phi|$ is the number of solutions that $\phi$ has.

And indeed, those 2 solutions are $(0,1,0)$ and $(1,0,1)$.


I have proven that this works for any logical expression. Does this have any use/bearing on $\mathsf{\#P}$ vs $\mathsf{NP}$?

$\endgroup$
  • $\begingroup$ Have you tried proven your reduction works in polynomial time? $\endgroup$ – dkaeae Jul 15 at 13:40
  • $\begingroup$ @dkaeae I can't code yet (Only just started learning python) I'm a maths graduate so really should have learned by now. In short, no. $\endgroup$ – Ben Crossley Jul 15 at 13:42
  • $\begingroup$ I know that the expansion of $\phi$ from it's factored form to the simplified form takes exponential time but then each step from here is polynomial. $\endgroup$ – Ben Crossley Jul 15 at 13:45
  • 1
    $\begingroup$ @BenCrossley Also, computational complexity theory (even theoretical CS in general) has little to do with coding (although you do need some good algorithmic intuition). $\endgroup$ – dkaeae Jul 15 at 14:06
  • 3
    $\begingroup$ I misunderstood what you meant by "simplify" then. That said, I don't think your question is answered in the way you think it was. You've not proven that this ($\# P$) problem is "equivalent in complexity" to an $NP$ problem. I don't see how your technique (for counting the number of satisfying assignments) could be implemented with "$NP$" complexity. $\endgroup$ – Tom van der Zanden Jul 15 at 14:17
4
$\begingroup$

As I have hinted at in the comments, that your reduction exists is not at all surprising. As in my answer to your previous question, your "Expand and simplify" part takes potentially exponential time and, thus, does not qualify as a polynomial-time reduction (which is the standard notion used to compare the classes in question). Exponential-time reductions here are irrelevant because both $\mathsf{NP}$ and $\#\mathsf{P}$ are contained in $\mathsf{EXP}$, so the reduction is powerful enough to solve the problems it should be reducing.

As to address the question in the title, notice the following: Let $P \in \mathsf{NP}$ be some problem, $S_P$ the solution set associated with $P$ (i.e., the $\{0,1\}^\ast \times \{0,1\}^\ast$ relation which, for instance, associates each $x \in P$ with its (poly-time verifiable) solutions), and $\#S_P\colon \{0,1\}^\ast \to \mathbb{N}_0$ be the counting problem associated with $S_P$, that is, $\#S_P(x) = |S_P(x)|$. For $P = \mathsf{SAT}$, for example, $S_P$ is simply the relation of formulas to their satisfiable assignments, and $\#S_P$ the number of satisfiable assigments. Then you can recast $P$ as the (decision) problem $\{ x \mid \#S_P(x) \ge 1 \}$. This means that having a procedure which counts solutions (i.e., computes $\#S_P \in \# \mathsf{P}$) directly yields something which decides $P \in \mathsf{NP}$.

Not only that, but notice that above we do not even actually use the value $\#S_P(x)$ other than to test that it is not zero. It is conceivable that we can use that accurate value towards solving problems much harder than $\mathsf{NP}$ (e.g., as Toda's theorem tells us; see David Richerby's answer). This gives us enough reason to believe that problems in $\#\mathsf{P}$ are, in general, much harder than those in $\mathsf{NP}$ (the most conspicuous candidates being the $\#\mathsf{P}$-complete problems).

$\endgroup$
  • 1
    $\begingroup$ $NP$ consists of decision problems, $\# P$ consists of counting problems. The statement $NP\subseteq \# P$ is very informal, and you should note this limitation. $\endgroup$ – Tom van der Zanden Jul 15 at 14:19
  • $\begingroup$ @TomvanderZanden Good catch, thanks. Rewrote entire second paragraph to make it formally correct. (The OP says they graduated in maths, so should have no problem with the formalities here.) $\endgroup$ – dkaeae Jul 15 at 14:55
2
$\begingroup$

By Toda's theorem, there are randomized reductions from every problem in the polynomial hierarchy to any #P-complete problem. As such, an NP algorithm for any #P-complete problem would be a huge deal.

However, your algorithm doesn't actually seem to use any nondeterminism, so either you've proven that P=#P (which implies P=NP along the way) or you've made a mistake somewhere.

$\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.