Sont $ Mathsf { # p} $ Problèmes plus difficiles que $ Mathsf {np} $ Problèmes

Question

J'ai une méthode pour résoudre le $ mathsf { # p} $ version de 3SAT d'une manière qui le réduit apparemment à un $ mathsf {np} $ problème. - Je n'ai pas de compréhension formelle de ces termes, je vais donc montrer un exemple ici.

Combien de solutions fait dollars ont?

Convertissez d'abord en polynôme booléen:dollars

Développer et simplifier (en utilisant, par exemple, $ x ^ 2 = x $ pour les valeurs booléennes):$$ phi = x_2 - x_1x_2 + x_1x_3 - x_2x_3 $$

Remplaçant $ x_1 = x_2 = x_3 = frac {1} {2} $ et multiplier par 2 $ ^ n $ où $ n $ est le nombre de variables:$$ | Phi | = 2 ^ n Left ( frac {1} {2} - frac {1} {4} + frac {1} {4} - frac {1} {4} droit) = 2 ^ 3 frac {1} {4} = 2 $$

où $ | phi | $ est le nombre de solutions qui $ phi $ a.

Et en effet, ces 2 solutions sont $(0,1,0)$ et $(1,0,1)$.

---

J'ai prouvé que cela fonctionne pour toute expression logique. Est-ce que cela a une utilisation / une incidence sur $ mathsf { # p} $ contre $ mathsf {np} $?