Pregunta

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}$?

No hay solución correcta

Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange
scroll top