Is The Counting Hierarchy Infinite? Threshold Circuits, Parallel Queries, And The Limits Of Pp

Defining the Counting Hierarchy

The counting hierarchy refers to a collection of complexity classes that categorize counting problems based on their computational difficulty. At the lowest level is the class PP, which contains decision problems where the number of accepting inputs can be counted in polynomial time by a nondeterministic Turing machine. The next level up is #P, the set of function problems that count the solutions to an NP problem. Higher levels of the hierarchy denote the complexity of counting for broader classes like Σ_i^p and Π_i^p in the polynomial hierarchy.

Problems in PP relate closely to both NP and BPP. While a PP machine cannot necessarily find or verify a solution as in NP, it can check multiple possible solutions at once using nondeterminism. Randomized algorithms and sampling also give Monte Carlo algorithms for estimating counts in PP. But despite these similarities, PP contains problems believed to be harder than either NP or BPP. The question of whether PP exactly equals these other classes remains a prominent open question.

Polynomial Hierarchy and Polynomial Time

The polynomial hierarchy defines classes Σ_i^P and Π_i^P that generalize NP and co-NP to higher levels. Specifically, Σ_1^P = NP, Π_1^P = co-NP, and for i > 1, Σ_i^P (Π_i^P) contains problems that can be solved in polynomial time by a nondeterministic (co-nondeterministic) Turing machine with access to an oracle for problems in Π_{i-1}^P (Σ_{i-1}^P).

For example, Σ_2^P allows the machine to make nondeterministic guesses, while querying an NP-complete oracle to verify conditions on those guesses. Higher levels allow nested alternating quantifiers over possible solutions. Counting the solutions at each level yields the classes #Σ_i^P and #Π_i^P within #P. If P = NP, then the entire polynomial hierarchy collapses to P. However, most evidence suggests this is unlikely.

The Counting Classes PP and #P

The class #P consists of function problems where the output is the number of accepting inputs for an NP problem. In other words, #P counts the witnesses that verify the existential quantifier for an NP problem. For example, #SAT counts the satisfying assignments for a boolean formula. Other examples include counting the cycles in a graph, the number of perfect matchings in a bipartite graph, the number of Hamiltonian cycles, and computing the permanent of a matrix.

In contrast, PP defines decision problems where the majority of nondeterministic paths accept or reject. So PP asks questions of the form “Does the number of accepting inputs exceed the number of rejecting inputs?”. For example, MajSAT takes a boolean formula as input and asks if more than half of all assignments satisfy it. By the properties of PP, we can obtain the exact solution count modulo small primes by asking about thresholds, then combine these to reconstruct the total count. The relationship between PP and #P mirrors that between NP and #P’s function problems.

The Power of Threshold Circuits

Threshold circuits are a natural model for problems in TC0, a small but still powerful class containing constant-depth, polynomial-size circuits with majority, modular counting, and other threshold gates. Despite their limitations, surprising results show threshold circuits can compute iterated matrix products, encode powerful counting principles, and even surpass generic Boolean circuits.

Definition and Examples of Threshold Circuits

A threshold gate outputs 1 if and only if a linear sum of its inputs exceeds some integer threshold value. For example, a majority gate outputs 1 if more than half its inputs are 1. A mod-q gate outputs 1 if the sum modulo q exceeds some value. Formulas in PP can be computed by polynomial-size, constant-depth threshold circuits based on iterating majority votes. Specific families like TC0, NC1, and ACC contain threshold gates together with small Boolean gates.

Threshold Circuit Families and Uniformity

When defining complexity classes from threshold circuits, different uniformity conditions affect their power. Nonuniform TC0 allows arbitrary polynomial-size constant-depth thresholds circuits with no constructability constraints. This contrasts with logspace-uniform TC0 requiring a logspace Turing machine to output each circuit. Logspace uniformity ensures closure under complement while allowing simulation by narrow branching programs.

In nonuniform models, tight lower bounds are known for specific functions in TC0. But for logspace-uniform TC0 and other restricted classes, the question of proving lower bounds against general Boolean circuits remains notoriously open. Separations are also not known between uniform TC0 and small circuit classes like NC1 and L.

Threshold Circuits for Iterated Matrix Product

The iterated matrix product problem multiplies a sequence of n x n matrices and outputs a specific entry of the result. Surprisingly, uniform TC0 can multiply n matrices in depth O(log n) using O(n3) gates. The circuit exploits modular counting gates and recursion to efficiently aggregate values along paths of the matrix product graph.

The iterative product algorithm shows how threshold circuits can dynamically route information and iteratively improve approximations. This goes beyond the limitations of straight-line formulas and constant-depth majority circuits. However, the complexity of matrix multiplication in TC0 remains open – no polylogarithmic depth circuit is known without superpolynomial size.

Parallel Queries and Counting Complexity

Parallel query algorithms use multiple processors to count the solutions to a problem more efficiently. But despite their power, inherent bottlenecks limit the maximum parallel speedup for counting problems compared to decision versions. Understanding these tradeoffs helps characterize the difficulty of problems in the counting hierarchy.

Definition of Parallel Query Algorithms

Parallel query algorithms apply in models like PPA RAM where processors share memory with arbitrary reads/writes. Given an NP problem, processors explore possible solution spaces and attempt to count witnesses by mutual exclusion, racing to claim solutions, or additive counting. Concurrent reads enable exponential parallel speedups.

However, processors may also bottleneck waiting to write out duplicate solutions found by others. So racing algorithms aim to minimize redundant work through randomization and early stopping. The maximum possible speedup varies based on differences in read and write complexity for problems.

Upper Bounds on Parallel Query Complexity

Although parallel queries can count solutions exponentially faster than sequential verification, limits still exist. Counting all witnesses to an NP problem can require up to linear time in the number of solutions. So for problems with exponentially many solutions, this gives at most a quadratic improvement over sequential algorithms.

In particular, Valiant and Vazirani showed that for #SAT formulas with up to n variables, parallel queries cannot verify all 2^n possible assignments faster than O(2^(n/2)). So there is at most a quadratic gap between the query and decision tree complexity. We believe this gap is tight – improving the bound further would yield major circuit lower bound breakthroughs.

Limits of Parallelization for Counting Problems

These tradeoffs demonstrate inherent barriers to counting in parallel models versus verifying witnesses sequentially. While nondeterminism enables checking multiple assignments simultaneously, the need to write out duplicate solutions creates bottlenecks not present for decision problems. So PPA RAM may give at most a polynomial speedup over the sequential complexity.

In terms of query complexity, Grover’s algorithm gives the optimal quadratic speedup for unstructured search, even with arbitrary parallelism. So while the counting hierarchy allows great expressiveness through nesting quantifiers, verifying witnesses fundamentally requires search – limiting potential parallel speedups versus decision classes like NP.

Open Questions on the Counting Hierarchy

Although much progress has been made in understanding the counting hierarchy, open questions remain about key relationships between counting classes. Resolving these questions could significantly advance knowledge about the capabilities and limits of efficient computation.

Whether PP Contains Problems Outside the Polynomial Hierarchy

A major open question is whether probabilistic polynomial time (BPP) with nondeterminism can solve counting problems fundamentally harder than the polynomial hierarchy. While BPP is contained in PH, the power of allowing nondeterminism in PP remains unclear. Proving containment either way would illuminate the roles of randomness and nondeterminism in amplified counting power.

If the Counting Hierarchy Collapses or Continues Infinitely

It is unknown if the counting hierarchy forms a proper infinite hierarchy or collapses at some point to a finite level. If P = NP, then #P = P and the entire counting hierarchy would collapse to P. But without this assumption, the hierarchy could continue indefinitely or converge at a higher level. Understanding this structure would further separate the hardness of counting from verifying.

The Role of Threshold Circuits in Separating Counting Classes

Threshold circuits can encode counting principles like majority votes far more efficiently than Boolean circuits, suggesting avenues to separate nested counting classes. For example, proving lower bounds on the depth of threshold circuits could separate nondeterministic counting in PP from deeper polynomial hierarchy levels. However, current techniques fall short of even separating TC0 from NC1.

As an alternative to depth bounds, understanding the power of weight-restricted threshold circuits could yield insights – for example, separating TC0 circuits based on the number of high-weight gates. Advances in these directions could uncover whether threshold circuits can access fundamentally different sources of hardness than traditional circuit models.

Example Python Code for a #P Problem

Here is Python code to define and count the solutions for #SAT, the canonical #P-complete problem:

“`python
def sharp_sat(formula):
if formula.is_empty():
return 0
elif formula.is_atom():
return 1
else:
left = sharp_sat(formula.left_subformula())
right = sharp_sat(formula.right_subformula())
return left*right # for AND gate
“`

This code recursively counts the satisfying assignments bottom-up by taking advantage of the decomposable structure of boolean formulas over AND gates. Multiplication accumulates counts from independently setting left and right subformulas. Exponential runtime remains unavoidable in the worst case, but memoization could be added to avoid recomputing on common subexpressions.