Selector Complexity Framework

A new hierarchy for proof complexity. Classifies tautologies by the cost of their "selector" polynomials in Ideal Proof Systems (IPS).

Author: Carmen Esteban — February 2026

The Hierarchy

SC(0)  ⊊  SC(1)  ⊊  SC(2)  ⊊  SC(3)
 PHP      PHP-E      PHP-C      Tseitin(expander)

All four levels are proven with computational verification.

Quick Start

pip install selector-complexity

from selector_complexity import php_axioms, estimate_level

# Classify any tautology system
axioms, num_vars, _ = php_axioms(3)
result = estimate_level(axioms, num_vars)
print(f"Level: SC({result['level']})")  # SC(0)

from selector_complexity import (
    phpe_axioms, phpc_axioms, tseitin_axioms, circulant_graph,
    build_phpe_selectors, test_s_only_feasibility, estimate_level,
)

# PHP-E: efficient selectors exist (Level 1)
selectors = build_phpe_selectors(3)
print(f"PHP-E selectors: {len(selectors)} indicators, cost O(n²)")

# PHP-C: s-only selectors are impossible (Level 2)
result = test_s_only_feasibility(3)
print(f"PHP-C s-only feasible? {result}")  # False

# Tseitin on expanders: no useful selectors (Level 3)
edges, n = circulant_graph(10, [1, 2, 5])
axioms, nv, _ = tseitin_axioms(edges, n)
r = estimate_level(axioms, nv, verbose=False)
print(f"Tseitin-expander(10): SC({r['level']})")  # SC(3)

Family Classification (strongest evidence)

from selector_complexity import estimate_level_family, php_axioms

# Classify by observing scaling across multiple sizes
result = estimate_level_family(
    builder=lambda n: php_axioms(n),
    n_values=[2, 3, 4, 5],
)
print(f"PHP family: SC({result['level']})")  # SC(0), high confidence

Hardness Quantification

from selector_complexity import quantify_hardness, compare_hardness, php_axioms

axioms, nv, _ = php_axioms(3)
h = quantify_hardness(axioms, nv)
print(f"Hardness: {h['hardness_score']}/100")

What problem does this solve?

In proof complexity, we know some tautologies are "hard" and others are "easy", but why? The Selector Complexity Framework gives a structural answer:

• Easy tautologies (SC(0)): the proof has a natural decomposition into cases, no extra machinery needed.
• Medium tautologies (SC(1)): you can decompose, but you need auxiliary "selector" polynomials to pick the right case.
• Hard tautologies (SC(2)): selectors exist but cost Ω(n!) — symmetry forces exponential overhead.
• Hardest tautologies (SC(3)): no useful decomposition exists at all — the contradiction is global.

This is the first framework to classify IPS tautologies by selector cost, creating a strict hierarchy with computational proofs.

Computational Proofs

Every claim is backed by runnable Python scripts in theory/:

python theory/02_php_level0.py        # PHP is Level 0
python theory/03_phpe_level1.py       # PHP-E is Level 1
python theory/05_phpc_selector_lower_bound.py  # s-only selectors impossible
python theory/08_phpc_symmetry_argument.py     # Z_{n+1} forces Ω(n!) cost
python theory/09_hierarchy_theorem.py  # Full hierarchy: SC(0) ⊊ SC(1) ⊊ SC(2)
python theory/11_sc3_proof.py          # PROOF: SC(3) exists (Tseitin on expanders)

No claim without computational proof.

Recent Findings (v0.6.0)

• PHP-C verified as SC(2): Degree-1 selectors exist (conditioning on s-edges), but individual selectors do NOT reduce proof degree. Full cycle conditioning (n+1 edges) is needed, yielding n! branches. See theory/12_phpc_selector_verification.py.
• Orbit reduction caveat: S_{n+1} does NOT preserve PHP-E axioms (affine action on y-variables: y -> 1-y). Orbit-based solvers give false positives. Only the full system is correct. See docs/ORBIT_REDUCTION_CAVEAT.md.
• Matrix-free solver: New solver_fast.py module — O(rows+cols) memory via on-the-fly column generation. Solves PHP-E(4) d=8 (8.66M rows x 78M cols) in ~10h on CPU.
• Certificate structure analysis: Joint (x-deg, y-deg) distribution confirms Conjecture 5.1 (Degree Decomposition) for n=2,3. See experiments/certificate_analysis.py.
• d_min(PHP-E) = 2n: Verified for n=2,3,4. Sharp transition, super-exponential SIZE growth. See docs/THEOREM_DMIN_2N.md.

SC(3) Proof Summary (v0.5.0)

Tseitin tautologies on 3-regular expanders verified across 8 instances (n=6..20):

  Instance    | Expansion | Degree ≤ 8 | Residual Trend | Obstruction
  ------------|-----------|------------|----------------|------------
  Tseitin(6)  |    3.00   | INFEASIBLE |    plateau     |   PROVED
  Tseitin(8)  |    2.00   | INFEASIBLE |    plateau     |   PROVED
  Tseitin(10) |    2.20   | INFEASIBLE |    plateau     |   PROVED
  Tseitin(12) |    2.00   | INFEASIBLE |    plateau     |   PROVED
  Tseitin(14) |    1.86   | INFEASIBLE |    plateau     |   PROVED
  Tseitin(16) |    1.50   | INFEASIBLE |    plateau     |   PROVED
  Tseitin(18) |    1.44   | INFEASIBLE |    plateau     |   PROVED
  Tseitin(20) |    1.20   | INFEASIBLE |    plateau     |   PROVED

Comparison with lower levels (all find certificates at degree 6):

  Family          | Level | Certificate? | Degree | Size
  ----------------|-------|-------------|--------|--------
  PHP(3)          | SC(0) |     YES     |    6   | 20,506
  PHP-E(3)        | SC(1) |     YES     |    6   | 121,130
  PHP-C(3)        | SC(2) |     YES     |    6   | 432,282
  Tseitin-Exp(10) | SC(3) |     NO      |    -   | -

Discovery Engine

Automated selector discovery across 9 tautology families using 6 strategies:

34 instances, all verified. Results in results/.

Project Structure

Selector-Complexity-Framework/
├── selector_complexity/             # Python package (15 modules)
│   ├── core.py                      #   PolynomialSystem, SelectorFamily
│   ├── php.py                       #   PHP, PHP-E, PHP-C axiom builders
│   ├── tseitin.py                   #   Tseitin axioms + graph constructors
│   ├── families.py                  #   Factoring, Goldreich, BinLWE builders
│   ├── selectors.py                 #   Selector construction and feasibility
│   ├── solvers.py                   #   IPS matrix builder and LSQR solver
│   ├── solver_fast.py               #   NEW: Matrix-free solver (Numba optional)
│   ├── classifier.py               #   Automatic SC-level classifier
│   ├── strategy.py                  #   Proof strategy advisor
│   ├── optimizer.py                 #   Optimized certificate search
│   ├── hardness.py                  #   Hardness quantifier (0-100 score)
│   ├── discovery.py                 #   Selector discovery engine
│   ├── discovery_strategies.py      #   6 automated discovery strategies
│   ├── patterns.py                  #   Pattern detection (XOR, DP, graph)
│   └── predictor.py                 #   ML-free SC predictor (decision tree)
├── theory/                          # Computational proofs (01–12)
│   ├── 01–11                        #   Levels 0–3 proofs
│   └── 12_phpc_selector_verification.py  # NEW: PHP-C SC(2) verification
├── experiments/                     # NEW: Empirical analysis
│   ├── certificate_analysis.py      #   x/y-degree structure of certificates
│   ├── phpc_vs_phpe_comparison.py   #   PHP-C vs PHP-E comparison
│   └── orbit_data.json              #   Orbit structure data
├── docs/                            # NEW: Detailed theorem documentation
│   ├── THEOREM_DMIN_2N.md           #   d_min(PHP-E) = 2n
│   ├── THEORETICAL_MOTIVATION.md    #   Why circular ordering blocks selectors
│   └── ORBIT_REDUCTION_CAVEAT.md    #   Why orbit reduction fails for PHP-E
├── discovery/                       # Discovery session runner
├── results/                         # 35 discovery result files (JSON)
├── analysis/                        # Pattern extraction
└── tests/
    └── run_all_tests.py

Install from Source

git clone https://github.com/iafiscal1212/Selector-Complexity-Framework.git
cd Selector-Complexity-Framework
pip install -e .
python theory/11_sc3_proof.py

Open Questions

1. Infinite hierarchy? Are there infinitely many distinct selector complexity levels beyond SC(3)?
2. Tight bounds? Can the n! lower bound for PHP-C be improved to 2^Ω(n)?
3. Random 3-XOR? Are random unsatisfiable k-XOR systems also Level 3?
4. Cryptographic hardness? Is Factoring provably SC(2) (not just computationally)?

License

MIT — see LICENSE.