Consulta Oracle obrigatória

Question

As variáveis $a,b,c\in\{0,1\}$, por isso $a^k, b^k, c^k \in \{0,1\}$

Quero passar uma consulta para um oráculo que retorne os coeficientes de cada termo $(1,a,b,c,ab,ac,bc,abc)$ na expansão de produtos como este $(1-a+ab)(1-b+bc)(b-bc)$.Poderia haver mais variáveis ​​e mais colchetes para expandir.

Preciso de uma única consulta FP para fazer isso ou algo mais?

---

editar:

Entrada: $(1-a+ab)(1-b+bc)$

Expandir: $a b^2 c - a b^2 - a b c + 2 a b - a + b c - b + 1$

Aplique a propriedade de idempotência: $a b c - a b - a b c + 2 a b - a + b c - b + 1$

Simplificar: $1 - a - b + ab +bc$

Extrair coeficientes: \begin{matriz} 1 & 1 \\ a & -1 \\ b & -1 \\ c & 0 \\ ab & 1 \\ ac & 0 \\ bc & 1 \\ abc & 0 \end{matriz}

Pergunta:Qual é o oráculo 'mais fraco' capaz de extrair os coeficientes acima da entrada?

Answer 1

Seu problema é #P-difícil.Na verdade, dada uma instância #SAT com variáveis $x_i$ e cláusulas $C_j$, deixar $\kappa_{i,b}$ ser o produto das cláusulas $C_j$ satisfeito pela atribuição de verdade $x_i=b$, e considere$$ P = \prod_i (\kappa_{i,0} + \kappa_{i,1}).$$O coeficiente de $\prod_j C_j$ em $P$ é o número de tarefas satisfatórias.

Na outra direção, o caso especial onde a fórmula de entrada é $\Pi\Sigma\Pi$ (isto é, o produto de polinômios) é #P-completo.Suponha que estejamos interessados ​​no coeficiente de algum monômio $m$ em $\prod_k P_k$, onde o $P_k$ são polinômios.Substitua zero em todas as variáveis ​​que não aparecem em $m$.Agora adivinhe um termo de cada $P_k$, e aceite se os termos juntos cobrirem $m$.