As I understand from the survey "Progress on Polynomial Identity Testing - II" a polynomial-time algorithm for solving PIT for $\Sigma \Pi \Sigma \Pi (2, r)$ is unknown.

However, there exists paper of Ankit Gupta "Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties" that gives a polynomial-time algorithm for this case modulo the following conjecture from this paper.

Conjecture Let $F_1, F_2, \ldots, F_k$ be finites sets of irreducible polynomials in $\mathbb{C}[x_0, \ldots, x_n]$ of degree at most $r$ such that $ \cap F_i = \varnothing$ and for every $Q_1, \ldots , Q_{k-1}$ from distinct sets there are polynomial $P_1, \ldots, P_c$ in the remaining set such that $V(Q_1, \ldots, Q_{k-1}) \subseteq \cup_i V(P_i)$. Then $\text{trdeg}_{\mathbb{C}}(\cup_i F_i) = \lambda(k,r,c)$ for some function $\lambda$.

This conjecture impies the existense of polynomial-time for PIT for $\Sigma \Pi \Sigma \Pi (k, r)$. As I understand for $k=2$ this conjecture holds. Note first that $V(Q_1)\subseteq \cup_i V(P_i)$ implies $V(Q_1)\subseteq V(P_j)$ for some $j$. Indeed, by Nullstellensatz $(P_1 \cdot P_2 \ldots \cdot P_c)^m = Q_1 \cdot H$ for some $m$ and $H$. Since $Q_1$ is irreducible this means that some $P_j$ is divided by $Q_1$.

So, now we have two sets of irreducible polynomials $F_1$ and $F_2$ such that $F_1 \cap F_2 = \varnothing$ and for every $P$ from one of this set there exists $Q$ from another set such that $V(P) \subseteq V(Q)$. Of course this means that both sets are trivial.

So, there exists a polynomial-time algortihm for solving PIT for $\Sigma \Pi \Sigma \Pi(2,r)$-circuits.

Am I wrong?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.