Oracle Requête requise

Question

Les variables $ a, b, c \ in \ \ {0,1 \} $ , donc $ a ^ k, b ^ k, c ^ k \ \ \ {0,1 \ \ \ \ \ \ \ span>

Je veux transmettre une requête à un oracle qui renvoie les coefficients de chaque terme $ (1, A, B, C, AB, AC, BC, ABC) $ Dans l'expansion de produits tels que celui-ci $ (1-A + AB) (1-B + BC) (B-BC) $ . Il pourrait y avoir plus de variables et plus de crochets pour se développer.

Est-ce que j'ai besoin d'une seule requête FP pour faire cela ou quelque chose de plus?

---

EDIT:

entrée: $ (1-a + ab) (1-b + bc) $

Développer: $ A B ^ 2 C - A B ^ 2 - A B C + 2 A B - A + B C - B + 1 $

Appliquer une propriété d'idempotence: $ A B C - A B - A B C + 2 A B - A + B C - B + 1 $

Simplifier: 1 $ - A - B + AB + BC $

extraire coefficients: \ commencez {matrix} 1 & 1 \\ a & -1 \\ b & -1 \\ c & 0 \\ ab & 1 \\ AC & 0 \\ bc & 1 \\ ABC & 0 \ fin {matrice}

Question: Quel est l'oracle "le plus faible" capable d'extraire les coefficients ci-dessus de l'entrée?

Answer 1

Votre problème est # p-dur. En effet, étant donné une instance #sat avec des variables $ x_i $ et clauses $ C_J $ , laisse $ \ kappa_ {i, b} $ Soyez le produit des clauses $ C_J $ satisfait de l'affectation de vérité $ x_i= b $ et envisagez $$ p=prod_i (\ kappa_ {i, 0} + \ kappa_ {i, 1}). $$ Le coefficient de $ \ prod_j c_j $ in $ p $ est le nombre de missions satisfaisantes.

Dans l'autre sens, le cas particulier où la formule d'entrée est $ \ pi \ sigma \ pi $ (c'est-à-dire que le produit des polynômes) est #p -Achevée. Supposons que nous soyons intéressés par le coefficient de certains monomiaux $ m $ in $ \ prod_k p_k $ , où La $ P_K $ sont des polynômes. Substituer zéro dans toutes les variables n'apparaissant pas dans $ M $ . Maintenant, devinez un terme de chaque $ p_k $ , et acceptez si les termes ensemble couvrent $ m $ . < / p>