Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling

Richard Cleve; Vahid R. Asadi

arxiv: 2604.02606 · v2 · submitted 2026-04-03 · 💻 cs.CC · cs.DS

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling

Vahid R. Asadi , Richard Cleve This is my paper

Pith reviewed 2026-05-13 19:07 UTC · model grok-4.3

classification 💻 cs.CC cs.DS

keywords TreeEvalCatalytic PebblingLogarithmic SpacePolynomial TimeSpace ComplexityComplexity Classes

0 comments

The pith

The Tree Evaluation Problem can be solved in polynomial time using almost logarithmic space through catalytic pebbling.

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

This paper gives the first algorithm for TreeEval that runs in polynomial time while using space O(log to the power 1 plus epsilon of n) for any epsilon greater than zero. It improves on earlier results that achieved close to logarithmic space but required superpolynomial time. The key is using catalytic space, so that only O(log n) bits need to be free while the rest can be overwritten and restored. A sympathetic reader would care because this brings TreeEval much closer to being solvable in logarithmic space, which would have implications for the relationship between P and L.

Core claim

The central discovery is an algorithm for TreeEval that, for any ε > 0, runs in polynomial time and uses O(log^{1 + ε} n) space, of which only O(log n) bits are free space and the rest is catalytic space.

What carries the argument

Catalytic pebbling, which enables trading additional catalytic space for a reduction in time complexity to polynomial while keeping free space at O(log n).

If this is right

TreeEval belongs to the class of problems solvable in polynomial time with almost logarithmic space.
The use of catalytic space allows the free space requirement to stay at O(log n) bits.
This provides a concrete time-space tradeoff that achieves polynomial time for the problem.
Prior non-polynomial time algorithms for near-log space are improved upon in the time dimension.

Where Pith is reading between the lines

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

Refinements of this catalytic pebbling technique could eventually place TreeEval in L.
The method may be adaptable to other problems that were candidates for separating P and L.
If TreeEval remains hard for logarithmic space, this would highlight the necessity of superpolynomial time for such problems.

Load-bearing premise

That the catalytic pebbling technique can be implemented without incurring extra time or space costs that would violate the polynomial time bound or the O(log n) free space limit.

What would settle it

A specific large instance of TreeEval where the algorithm either takes superpolynomial time or requires more than O(log^{1+ε}n) space for small ε would disprove the claim.

read the original abstract

The Tree Evaluation Problem ($\mathsf{TreeEval}$) is a computational problem originally proposed as a candidate to prove a separation between complexity classes $\mathsf{P}$ and $\mathsf{L}$. Recently, this problem has gained significant attention after Cook and Mertz (STOC 2024) showed that $\mathsf{TreeEval}$ can be solved using $O(\log n\log\log n)$ bits of space. Their algorithm, despite getting very close to showing $\mathsf{TreeEval} \in \mathsf{L}$, falls short, and in particular, it does not run in polynomial time. In this work, we present the first polynomial-time, almost logarithmic-space algorithm for $\mathsf{TreeEval}$. For any $\varepsilon>0$, our algorithm solves $\mathsf{TreeEval}$ in time $\mathrm{poly}(n)$ while using $O(\log^{1 +\varepsilon}n)$ space. Furthermore, our algorithm has the additional property that it requires only $O(\log n)$ bits of free space, and the rest can be catalytic space. Our approach is to trade off some (catalytic) space usage for a reduction in time complexity.

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 abstract claims the first poly-time O(log^{1+ε}n)-space algorithm for TreeEval using catalytic pebbling with only O(log n) free space, but without the construction we cannot check whether the time-space tradeoff actually works.

read the letter

The headline result is a polynomial-time algorithm for TreeEval that uses O(log^{1+ε}n) space for any ε>0, with the bulk of the space catalytic and only O(log n) bits free. This directly improves the Cook-Mertz STOC 2024 bound, which reached O(log n log log n) space but required super-polynomial time. The approach trades extra catalytic space to bring the running time down to poly(n), which is the main technical step forward here. If the pebbling construction holds, it narrows the remaining distance to showing TreeEval is in L, the original reason the problem was introduced. The abstract is clear on the parameters and on the catalytic split, which is a useful distinction for people tracking space-bounded results. The obvious limitation is that only the abstract is available. There is no recurrence, no description of the catalytic pebbling strategy, and no time analysis, so it is impossible to verify whether the claimed bounds are achieved without extra free-space overhead or super-polynomial factors hidden in the reuse. That makes the soundness hard to assess right now. The paper is aimed at complexity researchers working on catalytic space, pebbling, and potential P-L separations. Anyone following the TreeEval line of work will want to see the full version. It is worth sending to peer review once the details are written up, because the claim is concrete and builds on a recent result that already drew attention. A referee can then check the construction and the exact space-time accounting.

Referee Report

1 major / 0 minor

Summary. The paper claims the first polynomial-time algorithm for TreeEval that achieves almost-logarithmic space: for any ε>0 it runs in poly(n) time using O(log^{1+ε}n) space, with only O(log n) free bits and the remainder catalytic. The approach trades catalytic space against time to improve on the Cook-Mertz STOC 2024 O(log n log log n)-space algorithm, which did not run in polynomial time.

Significance. If the claimed bounds hold, the result would constitute a meaningful advance toward showing TreeEval ∈ L by demonstrating that space arbitrarily close to logarithmic is achievable in polynomial time under the catalytic-pebbling model. It would strengthen the catalog of space-time trade-offs obtainable from catalytic techniques and supply a concrete polynomial-time almost-log-space upper bound.

major comments (1)

[Abstract] Abstract: the manuscript supplies only the high-level claim and no algorithm description, recurrence, pebbling construction, or time analysis. Without these it is impossible to verify that the polynomial-time bound is obtained without hidden logarithmic factors or that the free-space requirement remains O(log n) after all catalytic reuse overheads are accounted for.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and for acknowledging the potential significance of our result toward TreeEval in L. We respond to the major comment below.

read point-by-point responses

Referee: [Abstract] Abstract: the manuscript supplies only the high-level claim and no algorithm description, recurrence, pebbling construction, or time analysis. Without these it is impossible to verify that the polynomial-time bound is obtained without hidden logarithmic factors or that the free-space requirement remains O(log n) after all catalytic reuse overheads are accounted for.

Authors: We agree that the abstract is intentionally high-level and does not contain the algorithm description, recurrence, pebbling construction, or detailed time analysis. The full manuscript provides these elements in the body, including the explicit catalytic pebbling strategy, the recurrence that governs the space-time tradeoff, and the analysis showing that the time remains polynomial with no hidden logarithmic factors while keeping free space at O(log n). To make verification easier from the abstract alone, we will expand it in the revision to include a brief outline of the pebbling approach and the resulting bounds. revision: partial

Circularity Check

0 steps flagged

No significant circularity

full rationale

The abstract states the main result as a direct algorithmic improvement over Cook and Mertz (STOC 2024) by trading catalytic space for polynomial time, without any equations, recurrences, fitted parameters, or self-citations that could reduce the claimed bound to its inputs by construction. No load-bearing derivation steps are present in the provided text, so the result is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract introduces no free parameters, no new invented entities, and relies only on standard assumptions of the catalytic space model and polynomial-time computation.

axioms (1)

domain assumption Catalytic space model permits reuse of auxiliary space without erasure costs beyond the stated free-space bound
The claimed O(log n) free space plus catalytic remainder is presented as valid under this model.

pith-pipeline@v0.9.0 · 5475 in / 1212 out tokens · 42382 ms · 2026-05-13T19:07:21.760419+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

For any ε>0, our algorithm solves TreeEval in time poly(n) while using O(log^{1+ε}n) space, with only O(log n) bits of free space and the rest catalytic.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.