Complexity Analogs of Rices Theorem

13 concepts4 papers1 proposal

In computability theory, Rice’s Theorem is a sweeping, absolute rule: any non-trivial semantic property of a program is undecidable. If you want to know whether an arbitrary piece of code eventually outputs the number 42, or if it computes a specific mathematical function, Rice's Theorem proves that no general algorithm can ever tell you.

For decades, complexity theorists have sought a "complexity-theoretic analog" to this rule. Instead of asking whether a property of a program is undecidable, they ask whether a property of a Boolean circuit is computationally hard (for example, hard for classes like UP or SPP).

However, building a universal version of Rice's Theorem for complexity theory hits an immediate mathematical wall. If every non-trivial property of a circuit were highly hard, it would force powerful complexity classes to collapse into much lower, simpler ones—a consequence that complexity theorists strongly believe is impossible.

The Collapse Barrier

To understand why a universal complexity analog fails, consider a simple "counting property" of a circuit, such as determining whether the number of satisfying inputs to a circuit is exactly 5. This is a non-trivial property because some circuits satisfy it and others do not.

If a complexity-theoretic Rice's Theorem held universally, even this simple property would have to be hard for a powerful counting class like SPP (the class of problems solvable by non-deterministic polynomial-time machines where the difference between accepting and rejecting paths is precisely controlled).

As explored by Lane A. Hemaspaandra and Jörg Rothe in Complexity-Theoretic Analogs of Rice's Theorem, requiring all counting properties to be SPP-hard creates an impossible paradox. If a trivial-looking property (like checking if a count equals 5) were SPP-hard, we could reduce highly complex SPP problems down to this simple property. This would force the powerful SPP class to be contained within the polynomial hierarchy—specifically inside $\text{P}^{\text{NP}}$.

Because such an inclusion would cause an unlikely collapse of the complexity hierarchy, a clean, all-or-nothing law for circuit properties cannot exist without constraints.

The Hardness Ceiling for Finite Properties

Why do these simple properties resist being hard? The answer lies in their mathematical structure.

In A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem, the authors demonstrate that properties defined by finite or cofinite sets of integers face a strict hardness ceiling. If a property only cares about a finite number of satisfying assignment counts, the problem is fundamentally bounded; it contains too little structural variety to encode the complex behavior of an SPP problem.

Instead of reaching high levels of hardness, these finite and cofinite properties are trapped low down in the Boolean Hierarchy. Trying to prove they are SPP-hard inevitably triggers a hierarchy collapse, proving that their simplicity is mathematically protected.

Bypassing the Barrier with P-Constructibility

To find where true computational hardness actually emerges, Hemaspaandra et al. identified a specific structural condition that guarantees hardness without causing a hierarchy collapse: P-constructible bi-infiniteness.

A counting property is P-constructibly bi-infinite if:

  1. Both the set of satisfying counts and its complement are infinite.
  2. A polynomial-time algorithm can efficiently generate or "find" elements within both the set and its complement at arbitrary scales.
P-Constructible Bi-Infinite Property:
[Count 0] -> [Count 1] -> [Count 2] -> ... -> [Count N]
   |            |            |                   |
   v            v            v                   v
(In Set)   (Out of Set)   (In Set)           (Efficiently findable at scale)

This condition provides the exact mechanism needed to prove hardness. Because an algorithm can easily construct valid instances of both the property and its complement at any size, a researcher can build a polynomial-time reduction. They can take a hard problem from a class like SPP and embed its logic into a circuit's structure, using the easily discoverable "in-set" and "out-of-set" counts as anchors to mirror the problem's truth values.

In Complexity-Theoretic Analogs of Rice's Theorem, the authors proved that any property meeting this structural criterion is unconditionally SPP-hard.

The Gap of Sparseness

This leaves a compelling open question at the frontier of the theory. What happens to properties that are infinite, but lack this clean, efficient constructibility?

As noted in A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem, if a property's satisfying instances are sparse or irregularly distributed, a polynomial-time machine cannot reliably find them to anchor a reduction. We currently do not know if these sparse, hidden properties share the same high hardness thresholds as their constructible counterparts.

This tension between sparseness and hierarchy behavior is a recurring theme in structural complexity. For example, in Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets, Lane A. Hemaspaandra and Jörg Rothe look at a parallel problem: how sparse complete sets affect the unambiguous complexity class UP. While sparse complete sets are known to collapse the polynomial hierarchy for NP, the restrictive, unique-path nature of UP prevents standard search-based reductions from working smoothly.

Across both domains, the lesson is the same: the geometry of a property—whether it is dense and easy to find, or sparse and isolated—dictates whether we can prove hardness, or whether the proof will be blocked by the rigid constraints of complexity hierarchy collapses.

Key Foundational Work

Complexity-Theoretic Analogs of Rice''s Theorem (1997) — contributed 6 concept elements to this direction.
A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem (1998) — contributed 4 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_complexity_class_collapse_constraints_434a48e6,
  title = {complexity class collapse constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/complexity-class-collapse-constraints/rdr_434a48e66d8e4c14aa2f0f2d41c1f536},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_complexity_class_collapse_constraints_434a48e6_v1,
  title = {complexity class collapse constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/complexity-class-collapse-constraints/rdr_434a48e66d8e4c14aa2f0f2d41c1f536/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake