<p>I'm looking for efficient algorithms for problems of the following type:</p>
<p>Let's say we have the variables <span class="math-container">$x_1,...,x_n$</span>.</p>
<p>Over these variables, we are given a function <span class="math-container">$p_1\cdot ... \cdot p_m$</span>, consisting of <span class="math-container">$m$</span> polynomials <span class="math-container">$p_1,...,p_m$</span>, each of which is a multivariate polynomial itself, of the form
<span class="math-container">$$
\sum_{\matrix{0\le i_1\le k\\...\\0\le i_n\le k} }a_{i_1,...,i_n} x_1^{i_1}\cdots x_n^{i_n}
$$</span>
, where <span class="math-container">$k$</span> is the highest degree appearing in any of the polynomials <span class="math-container">$p_1,...,p_m$</span>.</p>
<p>How do we efficiently extract a coefficient from <span class="math-container">$p_1\cdot ... \cdot p_m$</span>?</p>
<hr />
<p>Efficient in this case is relative, as the problem is  <a href="https://en.wikipedia.org/wiki/Sharp-P-completeness_of_01-permanent" rel="nofollow noreferrer">#P-complete</a> via <a href="https://en.wikipedia.org/wiki/Permanent_(mathematics)#MacMahon%27s_Master_Theorem" rel="nofollow noreferrer">MacMahon's Master Theorem</a> (it reduces the problem of calculating the permanent to extracting a coefficient of a function as given above).</p>
<p>Nevertheless it's a popular function, implemented in many CAS-systems, and with many applications in e.g. combinatorics.</p>
<p>I'm interested in both efficient algorithms (with complexity bounds) as well as theoretical complexity bounds.</p>

CC BY-SA 4.0
2019-08-27T07:50:14.513Z
When you wrote “in #P”, did you actually mean “#P-hard”?
Emil Jeřábek
CC BY-SA 4.0
2019-08-30T17:01:23.433Z
@EmilJeřábek Yes, that's right, more precisely it's #P-complete
Sudix
<time-complexity><polynomials>
Complexity of extracting a coefficient of a polynomial in multiple variables
Sudix
# Complexity of extracting a coefficient of a polynomial in multiple variables

(Asked by: username_0 on 2019-08-25)

I'm looking for efficient algorithms for problems of the following type:

Let's say we have the variables $x\_1,...,x\_n$.

Over these variables, we are given a function $p\_1\cdot ... \cdot p\_m$, consisting of $m$ polynomials $p\_1,...,p\_m$, each of which is a multivariate polynomial itself, of the form
$$
\sum\_{\matrix{0\le i\_1\le k\\...\\0\le i\_n\le k} }a\_{i\_1,...,i\_n} x\_1^{i\_1}\cdots x\_n^{i\_n}
$$
, where $k$ is the highest degree appearing in any of the polynomials $p\_1,...,p\_m$.

How do we efficiently extract a coefficient from $p\_1\cdot ... \cdot p\_m$?

---

Efficient in this case is relative, as the problem is [#P-complete](https://en.wikipedia.org/wiki/Sharp-P-completeness_of_01-permanent) via [MacMahon's Master Theorem](https://en.wikipedia.org/wiki/Permanent_(mathematics)#MacMahon%27s_Master_Theorem) (it reduces the problem of calculating the permanent to extracting a coefficient of a function as given above).

Nevertheless it's a popular function, implemented in many CAS-systems, and with many applications in e.g. combinatorics.

I'm interested in both efficient algorithms (with complexity bounds) as well as theoretical complexity bounds.

**Tags:** time-complexity, polynomials

> **Comments:**
> **username_1**: When you wrote “in #P”, did you actually mean “#P-hard”?  
> **username_0**: @EmilJeřábek Yes, that's right, more precisely it's #P-complete  

---

## 0 answers

