Alternation Hierarchies: Do They Reveal Fundamental Limits On Human Reasoning?
Alternation hierarchies are classifications of computational problems based on their inherent reasoning complexity. They arrange problems into a hierarchy based on the number of alternations between existential and universal quantifiers needed to express them. At the lowest level are problems that can be expressed without any alternations, like satisfiability (SAT). Higher levels require more intricate reasoning, with increasing quantifier alternations.
Studying these hierarchies reveals deep insights into the fundamental limits on computational reasoning. They help classify which problems can be efficiently solved by computer programs or human minds. Problems low in the hierarchy tend to be tractable, while those higher up often prove intractable. Where the boundary between easy and hard problems lies is a major open question.
Defining Alternation Hierarchies
Alternation hierarchies are composed of complexity classes containing decision problems of varying reasoning difficulty. Each class is defined by the number of alternations between existential (OR) and universal (AND) quantifiers needed to express a verification for the problem. For example:
- 0 alternations: Problems reducible to SAT, with no alternations.
- 1 alternation: Problems reducible to Quantified Boolean Formulas (QBF) with a single alternation block, such as Σ1 formulas with an initial existential block.
- k alternations: Problems reducible to QBFs with k alternation blocks between universal and existential quantifiers.
As the number of alternations increases, the complexity of logical reasoning required to solve problems in those classes also increases. This causes higher alternation classes to contain more computationally difficult problems.
Importance of Alternation Hierarchies
There are two main reasons why alternation hierarchies are important in computational complexity:
Reveal fundamental limits on reasoning
The alternation hierarchy provides insights into the inherent difficulty of logical reasoning problems. Problems low in the hierarchy are generally tractable, while those higher up prove exponentially more difficult. Each step up the hierarchy requires substantially more computational resources.
Understanding exactly where this exponential blowup in reasoning difficulty occurs reveals fundamental limitations on the power of human minds or computers to grapple with complex logic. Specifically, it suggests inherent constraints on our ability to efficiently comprehend and analyze intricate sequences of alternating quantifiers.
Provide classification of computational problems
Alternation hierarchies allow categorization of problems by their reasoning requirements. This enables better understanding of the complexity landscape – what types of reasoning tend to make problems hard or easy. It also facilitates discovering relationships and mappings between problems in different fields based on their reasoning complexity.
For instance, a problem in artificial intelligence could have equivalents in game theory or scheduling that require similar alternating reasoning. The alternation hierarchy provides a unifying language and classification system to understand these connections.
Alternation Hierarchy Background
There are several well-studied alternation hierarchies in computational complexity. These include the Polynomial Hierarchy, Boolean Hierarchy, and hierarchies of Quantified Boolean Formulas (QBFs).
Polynomial Hierarchy
The Polynomial Hierarchy arranges problems by the number of alternations between quantifiers in their polynomial-time verification process. As originally defined by Meyer and Stockmeyer, it contains these complexity classes:
- Σp0 = P – polynomial time problems
- Σpk = NP problems with k-1 alternating poly-time predicate blocks
- Πpk = Co-NP problems with k-1 alternating poly-time predicate blocks
Problems complete for various levels of this hierarchy include quantified Boolean formulas (QBF), stochastic programming, conformant planning, etc. Studying these complete problems provides lower bound proofs on the hierarchy.
Boolean Hierarchy
The Boolean Hierarchy, defined by Cai et al., arranges problems according to the complexity of Boolean formula value determination. Its lowest level 0 contains problems reducible to SAT. Higher levels add more alternating blocks of existential and universal quantified Boolean variables.
Key Boolean alternation complexity classes include:
- Σ1 = NP
- Π1 = Co-NP
- Σ2 = NPNP
- Π2 = Co-NPNP
The Boolean hierarchy strongest lower bound connection is to the polynomial hierarchy, with Σi ⊆ Σpi-1 and Πi ⊆ Πpi-1. Thus separating levels of the Boolean hierarchy also separates polynomial hierarchy levels.
Quantified Boolean Formulas
A Quantified Boolean Formula (QBF) attach quantifiers to a Boolean formula to produce expressions with different reasoning complexity based on quantifier alternations. They can be written in prenex normal form with a quantifier prefix attaching to a Boolean formula matrix. For example:
∃x∀y.(x ∧ ¬y) ∨ (¬x ∧ y)
Here ∃ and ∀ are alternating quantifiers over the Boolean variables. By its definition, a QBF with k alternations lies in the complexity class Σk in the polynomial hierarchy.
QBF satisfiability serves as a canonical complete problem for various alternation complexity classes. Its intractability has provided lower bound proofs onReasoning complexity of various alternation hierarchies.
Key Results on Bounded Alternation Classes
Significant work has gone into understanding the complexity of classes at small alternation depths in the major hierarchies. This includes both algorithms for solving problems in these classes and lower bound proofs on their inherent difficulty.
SAT algorithms
Boolean satisfiability (SAT) is the most-studied NP-complete problem, with extensive work on algorithms for solving it efficiently. Modern SAT solvers routinely tackle problem instances with millions of variables and clauses. However, these algorithms struggle as soon as quantification is added, even with a single alternation producing Σ2 and Π2 problems.
There has been progress in developing QBF solvers that use SAT-style search with additional heuristics to handle quantifier prefixes. However, unlike SAT, algorithms with worst-case guarantees for QBF have remained elusive. So while SAT itself may be easy, a single step up to problems like TQBF quickly becomes exponentially harder.
Proof complexity lower bounds
Proof complexity studies the inherent difficulty of verifying mathematical proofs. It provides lower bound results connected to alternation hierarchy separations. For instance, resolution is a simple yet limited proof system corresponding to SAT algorithms. Moving to more powerful proof systems like cutting planes and Frege systems captures the reasoning of higher polynomial hierarchy levels.
Intuitively, if more complex proof systems cannot efficiently certify a problem’s unsatisfiability, then algorithms will also struggle to solve that problem. This approach has shown immutable reasoning bottlenecks appear between alternation levels of the polynomial hierarchy, such as at Σ2 and Π2.
Open Questions
Despite substantial progress, open questions remain around alternation hierarchies and the limits they impose:
Precise relationships between hierarchies
While the Boolean hierarchy is known to qualitatively match the polynomial hierarchy, the precise mapping between them is unclear. Are problems complete for corresponding levels truly equivalent? Or does one hierarchy strictly subsume the other?
There are also interesting connections between alternation and other measures of complexity like circuit depth. Do circuit lower bounds lead to hierarchy separations? Such relationships may offer new approaches to proving hierarchy separations.
Additional separations or collapses
The lowest open levels of the polynomial hierarchy and Boolean hierarchy are at depth 3 and above. Do these higher complexity classes separate? Or unexpectedly collapse to lower levels contrary to the hierarchy thesis?
Resolving this critical question would substantially advance our understanding of the barriers faced by algorithms, automated reasoning engines, and human minds as quantifier alternations increase. The answers may reveal alternation hierarchies bottom out beyond small depths, or indeed march upward indefinitely.
