2
$\begingroup$

The variables $a,b,c \in \{0,1\}$, thus $a^k, b^k, c^k \in \{0,1\}$

I want to pass a query to an oracle that returns the coefficients of each term $(1,a,b,c,ab,ac,bc,abc)$ in the expansion of products such as this one $(1-a+ab)(1-b+bc)(b-bc)$. There could be more variables and more brackets to expand.

Do I require a single FP query to do this or something more?

edit:

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

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

Apply property of idempotence: $a b c - a b - a b c + 2 a b - a + b c - b + 1$

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

Extract coefficients: \begin{matrix} 1 & 1 \\ a & -1 \\ b & -1 \\ c & 0 \\ ab & 1 \\ ac & 0 \\ bc & 1 \\ abc & 0 \end{matrix}

Question: What is the 'weakest' oracle capable of extracting the coefficients above from the input?

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ In other words, you’re asking whether it’s possible to calculate individual coefficients in polynomial time. $\endgroup$
    – Yuval Filmus
    Mar 14, 2020 at 14:13
  • $\begingroup$ I don't understand your question. Can you specify separately: what is the problem you are trying to solve? (what is the input, and what is the desired output?) what function does the oracle implement? (what is the input to the oracle, and what is the output?) What's an FP query? When you say "do this", what is the "this"? Can you edit your question to specify the problem more systematically? $\endgroup$
    – D.W. ♦
    Mar 14, 2020 at 16:03
  • $\begingroup$ @YuvalFilmus I've edited the question for clarity. $\endgroup$
    – Ben Crossley
    Mar 14, 2020 at 18:24
  • $\begingroup$ @D.W. I've edited the question for clarity. $\endgroup$
    – Ben Crossley
    Mar 14, 2020 at 18:25
  • 1
    $\begingroup$ Yes, I now understand the problem. Please also make clear what the input could look like. Moreover, note that there could be many coefficients, so if you want an answer in polytime, you can only expect to get a single coefficient (more generally, polynomially many coefficients). $\endgroup$
    – Yuval Filmus
    Mar 15, 2020 at 15:03

1 Answer 1

Reset to default
2
$\begingroup$

Your problem is #P-hard. Indeed, given a #SAT instance with variables $x_i$ and clauses $C_j$, let $\kappa_{i,b}$ be the product of the clauses $C_j$ satisfied by the truth assignment $x_i=b$, and consider $$ P = \prod_i (\kappa_{i,0} + \kappa_{i,1}). $$ The coefficient of $\prod_j C_j$ in $P$ is the number of satisfying assignments.

In the other direction, the special case where the input formula is $\Pi\Sigma\Pi$ (that is, the product of polynomials) is #P-complete. Suppose that we are interested in the coefficient of some monomial $m$ in $\prod_k P_k$, where the $P_k$ are polynomials. Substitute zero in all variables not appearing in $m$. Now guess one term from each $P_k$, and accept if the terms together cover $m$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.