Conditional Collapse Results For The Polynomial Hierarchy From Algebraic Circuit Lower Bounds

The P=?NP Problem and Polynomial Hierarchy

The complexity classes P and NP represent fundamental problems in computer science related to the time required to solve computational problems on a deterministic and nondeterministic Turing machine respectively. P consists of decision problems that can be solved in polynomial time on a deterministic Turing machine while NP consists of decision problems where a solution can be verified in polynomial time on a deterministic Turing machine. The P vs NP problem asks whether all problems in NP can also be solved in polynomial time, i.e. whether P=NP. This is considered one of the most important open questions in theoretical computer science and mathematics.

The polynomial hierarchy (PH) generalizes the classes P and NP by considering alternations between existential and universal quantifiers in the definition of a complexity class. For example, the class Σ2P allows existential quantification over the accepting computations of an NP oracle machine. Higher levels in the PH have additional alternations between existential and universal quantifiers. It is known that P ⊆ NP ⊆ Σ2P ⊆ … ⊆ ΣkP ⊆ … where each containment is believed to be strict. Thus the polynomial hierarchy models increasing complexity. Understanding the relationship between different levels of PH would have significant implications for P vs NP and the inherent complexity of computational problems.

Algebraic Circuits for Formal Polynomials

An algebraic circuit is a directed acyclic graph used to compactly represent a formal polynomial. Each node in the circuit computes a polynomial based on its inputs, with addition and multiplication gates, and the output node computes the final polynomial represented by the overall circuit. Two important complexity measures for algebraic circuits are the depth, corresponding to the length of the longest path from an input to the output node, and the size, corresponding to the number of gates.

There has been significant research towards proving lower bounds on the depth and size required for algebraic circuits to compute explicit polynomials. However, major open problems remain in proving strong enough lower bounds that would have theoretical implications in complexity theory. Various methods have been devised for proving depth lower bounds for restricted kinds of circuits, with the strongest results holding for constant depth circuits computing an exponential polynomial.

Connections Between Circuits and Polynomial Hierarchy

Algebraic circuits have important connections to problems that lie in the polynomial hierarchy framework. Consider decision problems where the input consists of an algebraic circuit representing some polynomial over a finite field, and the problem asks whether the circuit satisfies certain properties. For example, computing the total degree of the polynomial encoded by the circuit. Many such algebraic circuit analysis problems naturally reside at various levels of PH based on the quantifiers in their definitions. In particular, there are examples where the problems are complete for classes like P, NP, coNP, Σ2P, Π2P indicating hardness for that entire complexity class.

Therefore, proving lower bounds on the depth requirement for algebraic circuits to compute a given family of explicit polynomials would imply conditional collapses in the polynomial hierarchy framework. Essentially, by showing limitations on the depth resources of circuits for problems residing in certain levels of PH, the entire PH would reduce downwards closer to P. This reveals a deep connection between the mathematical analysis of algebraic circuits and the complexity theory of problems in PH.

Collapse Results for Polynomial Hierarchy

In a major result by Håstad, it was proven that sufficiently strong lower bounds on the depth complexity of algebraic circuits for an explicit family of polynomials will cause the polynomial hierarchy to collapse down to level 3. Formally:

Theorem: If there exists a family {fn} of multivariate polynomials over a finite field F such that fn has degree d(n), where d(n) grows polynomially with n, and any algebraic circuit computing fn requires depth Ω(log d(n)), then PH = Σ3P

Thus the entire PH would collapse to having only 3 alternating quantifiers. This implies better algorithms for various problems across theory and AI applications based on this level 3 model. Further, it brings us closer to resolving problems like P vs NP since a collapse of PH is intuitively connected to P ≠ NP.

The key aspect of such depth lower bound proofs involves using a counting argument to argue that a shallow circuit cannot represent certain high degree polynomials due to limitations around the fan-in and fan-out of each gate in the circuit. By constructing an explicit family of polynomials with the right attributes, certain circuit depth restrictions can be proven barring the computation of that polynomial family. This technique serves as an approach for showing collapse of PH based on concrete algebraic circuits lower bounds, demonstrating the intriguing connection between these two domains.

Open Problems

While constant depth circuit lower bounds are known, improving such bounds for general algebraic circuits remains a major challenge in complexity theory. Any progress on this front conditional to PH collapses has significance in illuminating the nature of efficient computation. Further, better understanding the relationship between different levels of PH is an important direction, e.g. by constructing an oracle separation relative to which certain levels are provably unequal. Resolving such questions in the circuit and polynomial hierarchy settings continue to be among the deepest mysteries around the P vs NP problem.