{"id":"9ae13b67-203c-4f87-b207-b73d8abae559","arxiv_id":"2512.19060","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Computing the Strahler number of a binary tree is uNC^1-complete for term input, L-complete for pointer input, P-complete for DAG/TSLP input, and PSPACE-complete for acyclic derivation trees of CNF grammars.","lead":"This paper pinpoints the exact computational difficulty of computing the Strahler number—a measure of how 'bushy' a binary tree is—for several standard ways of encoding trees. The main result is that the problem is complete for uniform NC^1, with different completeness classes (L, P, NL, NP, PSPACE) for pointer, compressed, and grammar-derived tree representations.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The paper presents a careful complexity classification. I checked the main proof steps: the interval-function composition in Lemma 3.2 is correct; the circuit construction respects the TSLP dependency depth; the values involved are bounded by O(log n); and the hardness reductions from Boolean formula evaluation and monotone circuit value are standard. The only substantive dependency is the external balancing theorem [29, Theorem 5.6], which the reader also identified. This is a published, peer-reviewed result and not an internal inconsistency, so I do not treat it as a significant objection. The reader's verdict of ACCEPT with moderate confidence seems appropriate. Rather than manufacture a concern, I report an honest non-finding and propose a concrete verification of the external theorem as the one check most worth running.","tokens_in":30621,"tokens_out":38147,"duration_ms":376406,"concrete_test":"Independently verify [29, Theorem 5.6] by implementing the uTC0 construction and testing it on random binary trees up to n=10^6: confirm that the output is the ec-representation of a TSLP G with val(G)=t, size O(n), and dependency depth at most c log n. If this construction fails, the uNC1 upper bound of Theorem 3.1 would collapse.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim, Theorem 3.1, is backed by a coherent and detailed proof. The uNC1 upper bound rests on the external balancing theorem [29, Theorem 5.6], which is explicitly cited and is a published result; this is a legitimate dependency rather than an internal gap. The composition law for the interval functions [ℓ,h] in Lemma 3.2 checks out in all four cases, and the construction of the bounded-fan-in circuit B_{t,k} from the TSLP respects the required depth and uniformity constraints: gate dependencies are bounded by the TSLP depth, all values ℓ_A,h_A,st_A are O(log n), and the ec-representation is plausibly uTC0-computable. The hardness reductions are standard and the auxiliary claims, including the interval-function characterization of contexts, are internally consistent. I did not find a concrete flaw in the argument as written; the most vulnerable point remains the reliance on the imported balancing theorem, but that is not a demonstrated defect of this paper.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the computational complexity of deciding whether the Strahler number of a binary tree is at least a given threshold k, for several input representations. The main result is that for trees given in term representation, the problem St≥term is uNC1-complete. For pointer representation the problem is L-complete, and for DAG/TSLP representations it is P-complete. The paper also considers derivation trees of CNF grammars: deciding whether some derivation tree has Strahler number at least k is P-complete, while restricting to acyclic derivation trees gives NP-completeness for fixed k≥2 and PSPACE-completeness when k is part of the input. The proofs rely on a published tree-balancing theorem (Theorem 2.4), a new characterization of unary linear term functions in the Strahler algebra as interval functions [ℓ,h] (Lemma 3.2), and reductions from Boolean formula evaluation, graph accessibility, Majority, X3HS, and QBF.","tokens_in":30871,"tokens_out":52678,"duration_ms":490737,"significance":"If the results hold, they give a precise circuit-complexity classification of a natural tree parameter: computing the Strahler number of a term-encoded tree is exactly as hard as evaluating Boolean formulas in uNC1, an interesting example of tree evaluation over an infinite algebra. The interval-function composition lemma for the Strahler algebra is elegant and is likely to be useful in further work on grammar-based tree compression and register allocation. The paper also provides new complexity bounds for compressed representations and for derivation-tree problems that are relevant to recent work on group-DFA intersection and one-dimensional pushdown VASS. The main uNC1 upper bound is proved in detail, and the lower-bound reductions are mostly standard. If the P-hardness gap identified below is repaired, the paper would be a solid contribution to the field.","major_comments":[{"comment":"The lower bound for St≥dag is asserted in one sentence: 'one can reuse the reduction from the Boolean formula value problem in the proof of Theorem 3.1 in order to reduce the P-complete monotone Boolean circuit value problem to St≥dag.' This does not constitute a proof. In the Theorem 3.1 reduction, the threshold 2d±1 is derived from the depth of a balanced Boolean formula. For a general monotone circuit, the natural DAG encoding with the f∧/f∨ gadgets does not produce a value that separates true and false outputs by a single threshold. For example, for the monotone circuit C(x,y,z)=x∧(y∨z), the encoding yields value 4 both for input (0,1,1), where C evaluates to false, and for input (1,1,0), where C evaluates to true. Thus no k separates the two cases. A detailed reduction is needed; as written, the P-hardness of St≥dag and hence of St≥tslp is not established.","section":"Theorem 3.8(i), proof"}],"minor_comments":[{"comment":"The proof of Claim 3.6 is informal and depends heavily on Figure 2 and phrases like 'holes', 'spine nodes', and 'the crucial observation'. Since this claim is load-bearing for the uTC0-completeness of St≥4_term, please provide a formal inductive proof or at least a much more precise description of the tree construction and the cases |w|0≥n versus |w|0<n.","section":"Theorem 3.4, Claim 3.6"},{"comment":"In the grammar construction, the notation '[[O_a[I_b I_c]]]' appears to denote a nonterminal whose unique production is unary (X→Y), which is not allowed in the CNF definition. Please clarify the intended binary decomposition. Also, in the sentence 'we must have x_m∈S, y_m∉S, and z_m∉S for every j', the indices should be x_j, y_j, z_j.","section":"Theorem 4.1(ii)"},{"comment":"The L-hardness reduction from line graph accessibility is described in a single paragraph with no figure. A more formal description of the constructed tree and a proof of the equivalence st(t)=3 iff (u,v)∈E* would improve readability and verifiability.","section":"Theorem 3.7"},{"comment":"The 'gentle introduction' giving an O(log n log log n) space algorithm is sketchy and is not used later, since the uNC1 upper bound subsumes it. Consider shortening or removing it to avoid distracting the reader with an incomplete proof.","section":"Section 3, initial space-bound sketch"}],"recommendation":"major_revision","confidential_remarks":"The paper is generally well written, and the main uNC1-completeness proof is detailed and convincing. The interval-function characterization and the reductions for the grammar problems are also insightful. However, the P-hardness proof for the compressed (DAG/TSLP) representations is currently only a one-sentence assertion, and the natural way of instantiating it appears to fail. I would ask the authors to supply a full, correct reduction for Theorem 3.8(i). If that gap is repaired, I would support acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper settles something that was genuinely open, and the main proof is sound. I think it should go to peer review and likely be accepted after minor revisions.\n\nWhat's new: the exact uNC1-completeness of St_term^≥. The upper bound is the meat: it balances the input tree into a TSLP via a published theorem, then shows that every context in the Strahler algebra computes a simple [l,h] function. Lemma 3.2's composition law is verified in all four cases and is elegant. The lower bound via Buss's formula problem is clean. The rest — L-completeness for pointer representation, P-completeness for DAG/TSLP, and the grammar problems (P, NP, PSPACE) — rounds out the picture. These are natural questions and the answers are what you'd expect, but they're not in the literature, so it's a solid package.\n\nSoft spots: the upper bound depends on Theorem 2.4, a balancing result from the authors' own earlier paper. That's fine — it's peer-reviewed and the dependency is explicit. A referee should verify the uniformity claims around the ec-representation of the circuit, but nothing looks broken. Some auxiliary reductions are terse: the uAC0-computable function in Theorem 3.4 and the grammar constructions in Theorem 4.1 rely on figures and 'straightforward' steps. I'd like a bit more detail there, but I don't see a gap. The open k=3 boundary for uAC0 is stated honestly.\n\nCitation pattern looks appropriate; the authors cite the balancing theorem and Buss properly. No sign of circularity.\n\nThis is for a specialist audience — circuit complexity and compressed tree representations. I'd bring it to a working group if anyone cares about tree evaluation. Yes, it deserves a serious referee. I'd recommend accept with minor revisions.","headline":"Exact complexity classifications for Strahler numbers, with a sound uNC1-completeness proof; send to peer review.","tokens_in":31260,"tokens_out":1995,"would_cite":true,"duration_ms":21865,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that deciding whether a binary tree's Strahler number reaches a given threshold is uNC^1-complete for term-encoded trees, with L-, P-, NL-, NP-, and PSPACE-complete variants for other representations.","keywords":["Strahler number","Horton-Strahler number","circuit complexity","uniform NC^1","tree straight-line programs","register allocation","context-free grammars","PSPACE-completeness"],"falsifier":"Implement the reduction from Boolean formula evaluation: for balanced Boolean formulas of depth d, build the described term-encoded tree and compute its Strahler number; it should be exactly 2d+1 for true formulas and 2d for false formulas, and any deviation would falsify the uNC^1-hardness direction. Separately, brute-force the composition rule for [ℓ,h] functions over a large range of ℓ,h,m,i; a single counterexample would invalidate Lemma 3.2 and hence the circuit construction.","tokens_in":1701,"feed_emoji":"🌳","tokens_out":2860,"duration_ms":66959,"temperature":0.7,"pith_summary":"The Strahler number of a binary tree measures branching complexity and equals the minimum number of registers needed to evaluate the arithmetic expression the tree represents. This paper pinpoints the exact parallel complexity of deciding whether a tree has Strahler number at least k. For term-encoded binary trees the problem is complete for uniform NC^1, the class of problems solvable by logarithmic-depth, polynomial-size circuits with bounded fan-in. For pointer-encoded trees it is logspace-complete; for DAG- or TSLP-compressed representations it is P-complete. The paper also classifies grammar-based variants: asking whether a context-free grammar has a derivation tree with Strahler number at least k is P-complete, NP-complete for fixed k≥2 when the derivation tree must be acyclic, and PSPACE-complete for acyclic derivation trees when k is part of the input.","feed_headline":"Strahler-number check is as hard as Boolean formula evaluation","feed_subtitle":"Term-encoded trees: complete for uniform NC^1; pointers give L, compressed DAGs/TSLPs give P.","key_machinery":"The Strahler algebra S=(N,s,0) with binary operation s(x,y)=x+1 if x=y else max(x,y) is the central object. The key structural insight is that every binary context (a tree with one placeholder leaf) computes a unary function of the form [ℓ,h](x), and these interval-shaped functions are closed under composition with an explicit four-case rule (Lemma 3.2). This characterization, combined with a known uTC^0-computable tree-balancing theorem that converts a term-encoded tree into a logarithmic-depth tree straight-line program, allows the construction of a bounded-fan-in logarithmic-depth Boolean circuit for st(t)≥k, giving membership in uNC^1. For hardness, the simulated Boolean operations f∧ an","core_discovery":"The paper establishes exact complexity classifications for computing Strahler numbers. The central claim is that the decision problem St≥^term — given a binary tree as a term and a threshold k, is the Strahler number at least k? — is complete for uniform NC^1. The upper bound works by first balancing the input tree into a tree straight-line program of logarithmic depth using a known uTC^0-computable construction, then showing that every context in the Strahler algebra induces a unary function of the form [ℓ,h](x)=h if x<ℓ, h+1 if ℓ≤x≤h, and x if x>h; these functions compose according to a four-case rule, which lets the proof wire a bounded-fan-in circuit of logarithmic depth for each compari","pith_inferences":["If the uNC^1-completeness holds, Strahler-number evaluation is a natural tree-evaluation problem that is not logspace-computable in general unless L=uNC^1, contrasting with arithmetic expression evaluation, which is in L; the difference likely comes from the equality-triggering nonlinearity of the operation s.","The interval-function characterization suggests a reusable recipe: for any algebra whose contexts admit a compact parametric description closed under composition, tree balancing plus gate wiring yields a uNC^1 upper bound; this may transfer to other tree parameters with similar interval behavior.","The PSPACE-completeness of acyclic derivation-tree existence with k as input is a strong lower bound: it implies that imposing the acyclicity restriction on grammar derivation trees does not simplify the Strahler question, and that the constructed grammar effectively encodes quantified Boolean formulas.","A testable boundary question left open by the paper is whether St≥3^term lies in uAC^0; resolving this would refine the constant-depth threshold for Strahler-number checking and could shed light on the power of TC^0 for tree-embedding problems."],"forward_implications":["The Strahler-number decision problem for term-encoded trees is in uniform NC^1, hence in deterministic logspace, improving on previous polylogarithmic-time and logarithmic-space-with-small-factor bounds.","For pointer-encoded trees the problem is L-complete, so it is logspace-equivalent to graph accessibility in line graphs; term-encoded trees are genuinely harder in the circuit sense unless L = uNC^1.","For DAG- and TSLP-compressed trees the problem is P-complete, matching the hardness of the monotone circuit value problem; with a fixed threshold k, DAG-represented trees fall in UL∩coUL and TSLP-represented trees are NL-complete.","Deciding whether a CNF grammar has some derivation tree with Strahler number at least k is P-complete; with the acyclicity restriction, the problem is NP-complete for every fixed k≥2 and PSPACE-complete when k is part of the input.","An optimal register-allocation straight-line code for an arithmetic expression given as a term can be computed in uNC^1, since it suffices to compute the Strahler number of every subexpression."],"fun_headline_variants":["Strahler number for term trees is NC^1-complete","Strahler-number complexity: from NC^1 to PSPACE","Computing Strahler numbers: exact complexity classes","Strahler number: hard as Boolean formulas for terms","Strahler number: P-complete for grammars, PSPACE for acyclic"],"cache_read_input_tokens":32768,"weakest_assumption_plain":"The uNC^1 upper bound depends on importing a theorem that every binary tree of size n can be transformed in uniform TC^0 into a tree straight-line program of logarithmic depth and linear size; if that balancing theorem is wrong or not uTC^0-computable in the required uniformity, the upper bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["Strahler number for term trees is NC^1-complete","Strahler-number complexity: from NC^1 to PSPACE","Computing Strahler numbers: exact complexity classes","Strahler number: hard as Boolean formulas for terms","Strahler number: P-complete for grammars, PSPACE for acyclic"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000155,"raw_usage":{"total_tokens":1010,"prompt_tokens":665,"completion_tokens":345,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":409,"completion_tokens_details":{"reasoning_tokens":256}},"tokens_in":409,"tokens_out":345,"duration_ms":3939,"temperature":1.0,"reasoning_tokens":256,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T14:48:32.275913+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement the reduction from Boolean formula evaluation: for balanced Boolean formulas of depth d, build the described term-encoded tree and compute its Strahler number; it should be exactly 2d+1 for true formulas and 2d for false formulas, and any deviation would falsify the uNC^1-hardness direction. Separately, brute-force the composition rule for [ℓ,h] functions over a large range of ℓ,h,m,i; a single counterexample would invalidate Lemma 3.2 and hence the circuit construction.","supporting_citations":[],"review_version":1}