Complexity theory has a counting analogue of Rice's theorem. Rice's theorem says that every non-trivial question about what a program computes is undecidable. The analogue says that any non-trivial question of the form "does this Boolean circuit have a number of satisfying inputs that lies in the set $A$?" is computationally hard. The theory also draws a sharp line through the possible sets $A$. Finite sets, such as "exactly 5 solutions", sit low in the hierarchy of hard problems. Sets that are infinite in both directions and whose members can be listed efficiently, such as "an even number of solutions", are much harder. Nobody has checked whether this line has anything to do with how hard these questions are for actual solvers on actual circuits.
We propose to check it, and we expect the line to be the wrong variable. Our hypothesis is that, on real instances, the cost of deciding membership is governed by how close the true solution count falls to the nearest point where membership in $A$ flips. The theory's own hardness proofs work by forcing the count onto exactly such a flip point. To test the hypothesis we will build a sound, exact solver that stops counting as soon as the remaining uncertainty can no longer change the answer. We will also turn the published hardness reductions into a generator of deliberately adversarial instances.
Core Claim
Hemaspaandra and Rothe proved three results about counting properties: decision problems $\text{Counting}(A)=\{C : \#(C)\in A\}$, where $\#(C)$ is the number of satisfying assignments of circuit $C$. First, every non-trivial such property is hard for $\text{UP}_{O(1)}$, the problems solvable by nondeterministic machines with a constant number of accepting paths. Second, no finite or cofinite property is hard for $\text{SPP}$, a strong class of counting problems, unless $\text{SPP}\subseteq\text{P}^{\text{NP}}$. Third, every property whose members and non-members can both be generated in polynomial time at any scale ("P-constructibly bi-infinite") is $\text{SPP}$-hard (Complexity-Theoretic Analogs of Rice's Theorem; A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem).
These papers motivate our study: they are purely worst-case and contain no implementation. Their proof technique also supplies our method. Both the constant-setting reductions and the interval-contraction search operate on boundary events, the integers $n$ where membership in $A$ flips between $n$ and $n+1$.
We define the relative boundary gap of an instance as
$$\gamma(C,A)=\frac{\min_{b\in\partial A}|\#(C)-b|}{\max(\#(C),1)},$$
where $\partial A$ is the set of boundary points of $A$. The quantity $\gamma$ is the fraction by which the count could be wrong without changing the answer.
Our claim is that, for exact and sound decision procedures, $\log$ runtime is predicted far better by $\log(1/\gamma)$ than by the theoretical class of $A$ (finite, cofinite, or bi-infinite). The worst-case hardness of bi-infinite properties then shows up only because sets like "even" force $\gamma\approx 1/\#(C)$ on every instance. Sparse sets, whose hardness Hemaspaandra and Rothe leave open, should be easy on typical circuits and hard only when the count lands near a member.
The intuition comes from the cost of approximation. Separating $\#(C)$ from a boundary requires knowing the count to relative precision about $\gamma$. Hashing-based approximation needs on the order of $1/\gamma^2$ solver calls to reach that precision, while exact bound refinement has to close an interval of width about $\gamma\,\#(C)$.
Research Program
The first artifact is a gap-aware exact counter. It is a DPLL-style counter of the kind used in decision-priority projected counting (Projected Model Counting): a search that branches on variables and caches the counts of independent sub-formulas. We modify it to maintain a sound interval $[L,U]$ around $\#(C)$ at every moment. $L$ is the sum of the exact counts of subproblems already finished. $U$ adds, for each unexplored subproblem, $2$ raised to the number of its unassigned variables, tightened by unit propagation.
The solver halts the moment $[L,U]$ contains no boundary of $A$. A second change biases branching toward the subproblems whose resolution most shrinks the interval around the nearest boundary.
This is a generalisation of the Upper-Lower Watch idea in KOCO-SMC (Solving Satisfiability Modulo Counting Exactly with Probabilistic Circuits). KOCO-SMC tracks upper and lower probability bounds so it can prune against a single threshold. A single threshold is a one-boundary, cofinite property in our terms, so KOCO-SMC already covers the simplest case. Our contribution is to handle sets with arbitrarily many boundaries and to measure how cost depends on the gap.
The stopping test needs to answer one question about the set: "does $[L,U]$ contain both a member and a non-member of $A$?" For P-constructible sets this is a next-element computation. For sets where it is not, the test itself becomes the bottleneck. That gives an empirical counterpart to the constructibility hypothesis in Theorem 2.9 of Hemaspaandra and Rothe.
The second artifact is an instance generator built by implementing the constant-setting and interval-contraction reductions of A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem. The reductions take an NP, coNP or SPP instance and produce a circuit whose count sits at a boundary of $A$. So we obtain, for any target set, instances with minimal $\gamma$ by construction. We also record how large the reduction-generated circuits become. This answers the separate, previously unmeasured question of whether the polynomial overhead of these reductions leaves circuits within reach of modern solvers.
Direction 2, the empirical validation gap, acts here as the evaluation discipline rather than as a mechanism. It is the same gap documented for nearly-linear partitioning (A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning) and condition-number-independent gradient methods (Linear Convergence with Condition Number Independent Access of Full Gradients): proven bounds that hide constants and do not predict wall-clock behaviour. We treat the theoretical classification as a hypothesis to be tested against a measurable instance-level quantity.
Baselines
The do-nothing reference is full exact counting followed by a membership check. We run the same DPLL counter with the gap-based stopping rule disabled, and a d-DNNF compilation counter of the D2C kind described in Projected Model Counting. This is the strongest generic competitor because it is sound and fully general, and on easy instances it is hard to beat. Every method runs on the same instances, the same single core, the same 5,000-second timeout used in the SAT Competition main track (SAT Competition 2016: Recent Developments), and the same memory cap. The gap-aware solver beats this baseline if it decides strictly more instances within the timeout and the advantage grows with $\gamma$, as predicted.
For finite properties with small maximum element $m$, the theory-matched baseline is bounded enumeration. A plain CDCL SAT solver with blocking clauses finds up to $m+1$ models, and stopping at $m+1$ is exactly the bounded-query procedure implied by membership in the Boolean hierarchy. Our solver should never lose to it by more than a small constant factor. Losing badly on finite sets would falsify the claim that a single gap-driven procedure covers all set types.
The strongest existing bound-tracking method is KOCO-SMC's Upper-Lower Watch. It is restricted to threshold properties, so on that subset we compare against it directly. For reference, its paper reports solving 45% of 1,350 UAI-derived satisfiability-modulo-counting instances within 10 seconds and 80% within 20 minutes, against 40% for the best exact baselines after 3 hours (Solving Satisfiability Modulo Counting Exactly with Probabilistic Circuits). Those numbers are for its own task. No reported result was found on Lacuna for deciding $\text{Counting}(A)$ with multi-boundary sets.
The ablation that isolates our key ingredient keeps the anytime interval but uses a stopping rule that ignores $A$: the solver stops only when $U-L$ falls below a fixed width. A second ablation removes the boundary-directed branching while keeping the gap-based stop.
Why not just…?
Why not just run an exact model counter and check the count? This is the most serious threat. Wherever exact counting finishes quickly, early stopping saves little. The proposal stands or falls on the instances where full counting times out but the gap is large. The stratified analysis by $\gamma$ reports both sides of this explicitly: if speedups appear only in a negligible fraction of real instances, we will say so.
Why not just use an approximate counter, or MAXCOUNT-style self-composition? Approximate answers cannot certify membership near a boundary. KOCO-SMC reports that approximate competitors such as XOR-SMC and SAA returned wrong or unverifiable answers, while it never did. MAXCOUNT (Maximum Model Counting) solves an optimisation problem, not a membership decision. We still include a hashing-based approximate counter as a non-sound reference and measure its error rate as a function of $\gamma$. We predict errors concentrate at small $\gamma$, which is exactly where the reduction-generated instances live.
Why not just settle the sparse-set question theoretically? Proofs can establish worst-case hardness but not where real instances fall. The collapse result shows that some stronger unconditional statements are blocked unless $\text{SPP}\subseteq\text{P}^{\text{NP}}$. Our measurements complement that work rather than replace it.
Why not just learn a predictor of the answer? Learned predictors have no soundness. SATBench reports that o4-mini's accuracy drops to 65.0% on hard unsatisfiable puzzles (SATBench: Benchmarking LLMs Logical Reasoning via Automated Puzzle Generation from SAT Formulas), and exact count membership is strictly harder than that.
Proposed Experiments
The instance pool combines four sources:
- the Uniform Random 3-SAT, Boolean-circuit and five planning domains from Projected Model Counting;
- the UAI-derived instances of KOCO-SMC, with weights dropped to obtain unweighted counts;
- the QIF and backdoor formulas from Maximum Model Counting;
- the subset of SAT Competition 2016 instances whose exact counts can be obtained offline.
To this pool we add reduction-generated circuits for each target set. Ground-truth counts come from long offline runs, so $\gamma$ is known exactly.
The target sets span the theoretical landscape:
- singletons and small intervals, which are finite;
- thresholds, which are cofinite;
- residues modulo 2 and modulo 3, which are dense and bi-infinite;
- powers of two and doubly exponential sequences, which are sparse but constructible;
- a set defined by membership in a hard auxiliary language, which is sparse with an expensive interval test.
Metrics are instances decided within the timeout, PAR-2 score (mean runtime with each timeout counted as twice the timeout), and median runtime per $\gamma$ decile.
The first decisive check is a regression of log runtime on $\log(1/\gamma)$ versus on indicators for the theoretical set class, compared by held-out $R^2$ on matched instances. The hypothesis fails if the class indicators explain as much variance as the gap, or more.
The second check asks whether reduction-generated instances are the hardest instances for every sound method, and whether their hardness is fully accounted for by their minimal $\gamma$ once circuit size is controlled.
The third check is whether sparse constructible sets are easy on natural instances. We expect them to be easy on most natural instances and hard only in the small-$\gamma$ tail, a pattern the worst-case theory cannot express.
The fourth check measures how circuit size grows across interval-contraction steps, to establish whether the published reductions yield solver-tractable circuits at all.
References
- Complexity-Theoretic Analogs of Rice''s Theorem
- A second step towards complexity-theoretic analogs of Rice's Theorem
- Projected Model Counting
- Solving Satisfiability Modulo Counting Exactly with Probabilistic Circuits
- A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem
- A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
- Linear Convergence with Condition Number Independent Access of Full Gradients
- SAT Competition 2016: Recent Developments
- Maximum Model Counting
- SATBench: Benchmarking LLMs Logical Reasoning via Automated Puzzle Generation from SAT Formulas