On the Complexity of Determinations

Joseph M. Hellerstein

arxiv: 2603.28031 · v3 · submitted 2026-03-30 · 💻 cs.CC

On the Complexity of Determinations

Joseph M. Hellerstein This is my paper

Pith reviewed 2026-05-14 01:43 UTC · model grok-4.3

classification 💻 cs.CC

keywords determination depthpolynomial hierarchycommitment layersrelational complexitycircuit depthonline computationPSPACEsequential cost

0 comments

The pith

Relational tasks require a minimum number of sequential commitment layers that no amount of extra computation can reduce.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces determination depth as the smallest number of sequential layers of irrevocable commitments needed to pick one valid output from a relation that may have many. It shows that for some relational tasks the commitments themselves are simple constant-time lookups, yet shrinking the number of layers forces an exponential increase in the width of parallel computation. A conservation law establishes that adding power to the commitments themselves does not lower the total sequential cost; it merely converts determination layers into ordinary circuit depth. When the relational specification is given by a circuit, the resulting hierarchy of determination depths is exactly as hard as the polynomial hierarchy: complete for each fixed level Σ_{2k}^P and PSPACE-complete when the depth is unbounded. In the online setting the depth remains fully irreducible regardless of how much computation occurs between commitment layers.

Core claim

Determination depth is the minimum number of sequential layers of irrevocable commitments required to select a single valid output from a relational specification. For circuit-encoded specifications this depth hierarchy is Σ_{2k}^P-complete for each fixed k and PSPACE-complete for unbounded depth. No amount of intervening computation can reduce the number of layers in the online setting, and a conservation law shows that enriching commitments merely relabels determination layers as circuit depth while preserving total sequential cost.

What carries the argument

Determination depth: the minimum number of sequential layers of irrevocable commitments needed to select one valid output from a relation.

If this is right

Enriching commitments with extra computation converts determination layers into ordinary circuit depth without lowering the total sequential cost.
For any fixed determination depth 2k the problem of finding a valid output is complete for Σ_{2k}^P.
Unbounded determination depth captures exactly the PSPACE-complete problems.
In any online setting, unlimited computation between commitment layers cannot reduce their number.
Certain relational tasks admit constant-time commitment lookups but force exponential width when depth is reduced.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The separation between determination depth and circuit depth may impose limits on streaming or online algorithms that must commit early without later revision.
If the conservation law extends to other models, it could unify measures of sequential cost across circuit, relational, and query complexity.
The hierarchy suggests that parallel width and sequential commitment layers trade off in a way that might be observable in practical database or verification systems.
Testing whether real-world relational specifications exhibit the predicted depth-width trade-off would require constructing explicit families of relations with controlled commitment cost.

Load-bearing premise

Relational tasks exist whose commitments are constant-time table lookups yet require exponential parallel width to compensate for any reduction in depth, and the conservation law holds without additional hidden costs when commitments are enriched.

What would settle it

A concrete relational task for which the number of commitment layers can be reduced without an exponential blow-up in parallel width, or an online determination problem in which unlimited computation between layers demonstrably collapses their number.

read the original abstract

Classical complexity theory measures the cost of computing a function, but many computational tasks require committing to one valid output among several. We introduce determination depth -- the minimum number of sequential layers of irrevocable commitments needed to select a single valid output -- and show that no amount of computation can eliminate this cost. We exhibit relational tasks whose commitments are constant-time table lookups yet require exponential parallel width to compensate for any reduction in depth. A conservation law shows that enriching commitments merely relabels determination layers as circuit depth, preserving the total sequential cost. For circuit-encoded specifications, the resulting depth hierarchy captures the polynomial hierarchy ($\Sigma_{2k}^P$-complete for each fixed $k$, PSPACE-complete for unbounded $k$). In the online setting, determination depth is fully irreducible: unlimited computation between commitment layers cannot reduce their number.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper introduces determination depth as a commitment-layer measure that it claims exactly matches the polynomial hierarchy, but the absence of any proofs or constructions leaves the central claims uncheckable.

read the letter

The main new thing is the definition of determination depth: the minimum number of sequential layers of irrevocable commitments required to pick one valid output from a relational task that may have many. The paper argues this cost cannot be removed by extra computation, that certain tasks need exponential parallel width to trade off against depth, and that a conservation law lets you relabel enriched commitments as circuit depth while keeping total sequential cost fixed. For circuit-encoded specs this is supposed to give exact completeness results: Sigma_2k^P-complete for each fixed k and PSPACE-complete when k is unbounded. In the online case the depth is claimed to be fully irreducible. That framing is a clean way to separate commitment cost from ordinary computation and to connect it to existing hierarchy notions. The conservation-law idea is the part that could be useful if it holds, because it tries to show that sequential cost is preserved across different representations of the same task. The soft spots are large and central. The abstract states the equivalences and the conservation law but supplies no proof sketches, no small examples, and no concrete relational task that actually requires exponential width to reduce depth. Without those it is impossible to verify whether the relabeling in the conservation law really adds no hidden sequential cost when commitments are enriched, or whether the claimed completeness results follow from the new definition rather than from prior results. The stress-test concern about enriched commitments potentially introducing extra layers not captured by simple relabeling is therefore live; nothing in the text rules it out. This is the kind of paper that might interest complexity theorists who work on non-deterministic or multi-output problems and want a fresh organizing principle. A reader willing to invest time in the full proofs could get value if the derivations close the gaps, but the current version is too thin to stand on its own. I would send it to peer review so the authors can supply the missing constructions and check the conservation law against concrete cases; the idea is worth testing even if it needs substantial revision.

Referee Report

3 major / 1 minor

Summary. The paper introduces determination depth as the minimum number of sequential layers of irrevocable commitments required to select one valid output from a relational task. It claims that no amount of additional computation can reduce this depth, exhibits relational tasks whose commitments are constant-time table lookups but require exponential parallel width to compensate for depth reductions, proves a conservation law showing that enriching commitments merely relabels determination layers as circuit depth while preserving total sequential cost, and establishes that for circuit-encoded specifications the resulting depth hierarchy captures the polynomial hierarchy (Σ_{2k}^P-complete for each fixed k, PSPACE-complete for unbounded k). In the online setting, determination depth is claimed to be fully irreducible.

Significance. If the central claims hold, the work introduces a new complexity measure focused on commitment layers that is irreducible by computation and directly corresponds to the polynomial hierarchy via a conservation law. This could provide a fresh perspective on tasks requiring selection among multiple valid outputs, with potential implications for online algorithms and circuit complexity. The explicit linkage to Σ_{2k}^P and PSPACE completeness, along with the parameter-free conservation law, would be notable strengths if supported by the missing constructions.

major comments (3)

[Abstract, §3] Abstract and §3 (presumed central section on conservation law): the claim that enriching commitments 'merely relabels determination layers as circuit depth, preserving the total sequential cost' is load-bearing for the hierarchy equivalence but rests on an unshown argument that enriched commitments (e.g., replacing table lookups with non-constant-depth circuits) incur no additional irrevocable commitment layers. No explicit relational task construction or relabeling proof is provided to confirm cost preservation in the online setting.
[Abstract] Abstract: the assertion that relational tasks exist with constant-time commitments yet requiring exponential parallel width for any depth reduction is central to the irreducibility claim, but no concrete example task, width lower-bound derivation, or error-bound analysis is given; this creates a derivation gap for the strongest claim that determination depth captures the polynomial hierarchy.
[Abstract] Abstract: the completeness results (Σ_{2k}^P-complete for fixed k, PSPACE-complete for unbounded k) are stated without proof sketches, reduction constructions, or verification that the circuit-encoded specifications satisfy the constant-time commitment assumption; the absence of these details makes the hierarchy capture claim unverifiable from the provided text.

minor comments (1)

[Introduction] Notation for determination depth and commitment layers should be defined with a formal equation or inductive definition early in the paper to avoid ambiguity in later sections.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We agree that the central claims require more explicit constructions and details to be fully verifiable, and we will revise the paper accordingly.

read point-by-point responses

Referee: [Abstract, §3] Abstract and §3 (presumed central section on conservation law): the claim that enriching commitments 'merely relabels determination layers as circuit depth, preserving the total sequential cost' is load-bearing for the hierarchy equivalence but rests on an unshown argument that enriched commitments (e.g., replacing table lookups with non-constant-depth circuits) incur no additional irrevocable commitment layers. No explicit relational task construction or relabeling proof is provided to confirm cost preservation in the online setting.

Authors: We acknowledge that the conservation law in §3 was presented at a high level. In the revised manuscript we will supply an explicit relational task construction together with the full relabeling argument, showing that enriching commitments from constant-time lookups to non-constant-depth circuits adds only circuit depth while leaving the number of determination layers unchanged. The argument will be verified directly in the online setting. revision: yes
Referee: [Abstract] Abstract: the assertion that relational tasks exist with constant-time commitments yet requiring exponential parallel width for any depth reduction is central to the irreducibility claim, but no concrete example task, width lower-bound derivation, or error-bound analysis is given; this creates a derivation gap for the strongest claim that determination depth captures the polynomial hierarchy.

Authors: We will add a concrete relational task (a layered quantified-boolean-formula variant whose commitments are constant-time table lookups) together with the exponential-width lower-bound derivation and the accompanying error-bound analysis. These additions will appear in the main body and will directly support the irreducibility claim. revision: yes
Referee: [Abstract] Abstract: the completeness results (Σ_{2k}^P-complete for fixed k, PSPACE-complete for unbounded k) are stated without proof sketches, reduction constructions, or verification that the circuit-encoded specifications satisfy the constant-time commitment assumption; the absence of these details makes the hierarchy capture claim unverifiable from the provided text.

Authors: The completeness results rest on reductions that are only sketched in the current text. In the revision we will expand the sketches into explicit reduction constructions from Σ_{2k}^P-complete problems, include verification that the circuit-encoded specifications obey the constant-time commitment assumption, and place the full arguments in a dedicated section or appendix. revision: yes

Circularity Check

0 steps flagged

No circularity detected; derivation introduces independent measure and derives properties from it

full rationale

The paper defines determination depth as a new concept (minimum sequential irrevocable commitment layers) and states a conservation law that relabels enriched commitments as circuit depth while preserving total sequential cost. It then claims this captures the polynomial hierarchy for circuit-encoded specifications. No equations, self-citations, or prior results from the same authors are quoted that reduce the central claims to fitted inputs or definitions by construction. The abstract presents the hierarchy equivalence and irreducibility as consequences of the new definition and conservation law rather than tautological renamings or load-bearing self-references. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claims rest on the existence of relational tasks with the stated commitment properties and on standard complexity-theoretic background; no numerical free parameters are introduced, but the new determination depth concept functions as an invented organizing entity.

axioms (2)

domain assumption Relational tasks exist whose commitments can be realized by constant-time table lookups.
Invoked to exhibit the exponential parallel width requirement when depth is reduced.
standard math Standard definitions of circuit depth and the polynomial hierarchy apply without modification.
Used to establish the claimed completeness results for the depth hierarchy.

invented entities (1)

determination depth no independent evidence
purpose: Quantifies the minimum sequential layers of irrevocable commitments needed to select one valid output.
Newly defined measure whose properties drive the conservation law and hierarchy results.

pith-pipeline@v0.9.0 · 5421 in / 1546 out tokens · 43429 ms · 2026-05-14T01:43:58.356017+00:00 · methodology

On the Complexity of Determinations

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)