we-solve (beta)

CS-30 · computer science · mathematics · Computational complexity

L = P Problem

Status OpenLLM status Open unverified

Statement

Definitions and mathematical statement

In the standard Turing-machine model, $\mathsf L=\mathsf{DSPACE}(\log n)$ counts work-tape space but not read-only input cells. The class $\mathsf P$ consists of total deterministic polynomial-time deciders. The equality question is \[ \forall L\in\mathsf P\ \exists\text{ deterministic decider for }L \text{ using }O(\log n)\text{ work space}. \] The algorithm and constants may depend on the language. A fixed polynomial saving in space, or a logarithmic-space procedure with advice, does not establish the stated equality.

Formulation and concept references: [S1].

Short English statement

Can every polynomial-time decision problem be solved using only logarithmically much working memory?

Sources

Statement licence: CC-BY-4.0 · Source file

Contributions 2

CS-30-A2 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for CS-30

Derandomization of bounded-error randomized logarithmic space does not place every polynomial-time language in deterministic logarithmic space. The full equality with $\mathrm P$ is consequently outside the claim.

L = P Problem

OpenAI's claim

OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 103; 2026-09-23), the asserted result is that polynomial-time randomized logarithmic space can be simulated deterministically in logarithmic space, giving $\mathrm L=\mathrm{RL}=\mathrm{BPL}$.

Mathematical statement of the claimed result

Manuscript 1.
For uniform polynomial-time, logarithmic-work-space Turing machines, the claimed complexity-class equality is \[ \mathrm L=\mathrm{RL}=\mathrm{BPL}. \] More quantitatively, fix any randomized machine $\mathcal M$ of polynomial worst-case time and $O(\log(n+2))$ work space. Given input $x$ of length $n$ and unary $1^q$, $q\ge1$, a deterministic algorithm is claimed to output an integer $0\le a\le2^{q+2}$ satisfying \[ |a2^{-(q+2)}-p_{\mathcal M}(x)|\le2^{-q} \] in $O(\log(n+2)+q)$ work space and $(n+2)^{O(1)}2^{O(q)}$ time. Constants depend only on the fixed machine.

Outline of the argument

For manuscript 1 (family 103; 2026-09-23), stochastic atoms are assembled with controlled numerical error and bounded suspended storage. Slice-mixing walks are generated without retaining their endpoints, and a fixed bounded-resource interpreter makes the deterministic simulation uniform over source machines.

Formal verification

No Lean formalization is listed at this snapshot for manuscript 1 (family 103; 2026-09-23).

This site has not executed the Lean code. Described statement coverage is not an independent proof check.

Status caveat

The manuscripts were produced by an internal OpenAI model. OpenAI cautions that results without formalization can contain mistakes. This site has not independently checked the proofs; the label records the scope of OpenAI's claim.

Sources

Go to contribution →

CS-30-A1 · No claim recorded · LLM-generated · gpt 6 astra pro ·

gpt 6 astra pro attempt on CS-30

L = P Problem

Definitions and mathematical statement

In the standard Turing-machine model, $\mathsf L=\mathsf{DSPACE}(\log n)$ counts work-tape space but not read-only input cells. The class $\mathsf P$ consists of total deterministic polynomial-time deciders. The equality question is \[ \forall L\in\mathsf P\ \exists\text{ deterministic decider for }L \text{ using }O(\log n)\text{ work space}. \] The algorithm and constants may depend on the language. A fixed polynomial saving in space, or a logarithmic-space procedure with advice, does not establish the stated equality.

Formulation and concept references: [S1].

Short English statement

Can every polynomial-time decision problem be solved using only logarithmically much working memory?

Research attempt

Current frontier.
Circuit value is complete for $\mathsf P$ under deterministic log-space reductions, so a log-space evaluator for general circuits would settle the equality in the stated uniform model [S1], Theorem 6.1. Williams proves a deterministic time-$t$ simulation in $O(\sqrt{t\log t})$ space; substituting $t=n^c$ does not give logarithmic space [E1], Theorem 1.1. Pyne--Tell's March 2026 revision investigates composition with simultaneous time and space constraints, rather than an unrestricted collapse of $\mathsf P$ to $\mathsf L$ [E2]. These results motivate reevaluation instead of retaining all intermediate values, but do not justify iterating a space saving as though it were a time saving.
Attack route.
Recursive reevaluation needs a way to compress unresolved dependencies. Iterating a time--space simulation needs a new bound on the time of the intermediate simulator. A frontier method needs a representation with few computed values still relevant. We pursue the last route, remove an avoidable logarithmic factor from its storage accounting, and then test whether graph ordering alone could supply the missing bound.
Attempt: store values and recompute addresses.
Take a fan-in-two Boolean circuit with $N$ gates and encoded length $M$, together with an explicitly supplied topological ordering $v_1,\ldots,v_N$. The ordering may instead be generated in log space. Append an output-copy gate if necessary so that the output is evaluated last. Define \begin{equation}\label{wsref-0-72-36-30-3a-66-72-6f-6e-74-69-65-72} F_i=\{v_j:j\le i,\ \text{$v_j$ has a successor $v_\ell$ with $\ell>i$}\}, \qquad w=\max_{0\le i\le N}|F_i|. \end{equation} Input gates are included; counting their rereadable values only weakens the bound.

\begin{notebooklemma} An ordered circuit of frontier width $w$ can be evaluated deterministically in $O(w+\log M)$ work space and time polynomial in $M$. The algorithm is uniform, and its polynomial time exponent is independent of $w$. \end{notebooklemma}

Proof: After step $i$, store exactly the values of $F_i$, in the supplied order. Do not store gate identifiers beside the values. Membership of a given gate in $F_i$ is decidable by scanning the input and its ordering with $O(\log M)$-bit counters. Its rank in $F_i$ is found by counting earlier members. The rescans have polynomial cost and require no recursive graph traversal.

Before evaluating $v_i$, every predecessor belongs to $F_{i-1}$: it has the unprocessed successor $v_i$. Retrieve its value by its computed rank. Build a second buffer for $F_i$, copying surviving values and appending the new value if it remains live. Each buffer has at most $w+1$ bits. A constant number of gate indices and scan counters require $O(\log M)$ additional bits. Output the last value. All nested input scans have fixed depth and each buffer traversal has length at most $N$, proving the time claim. ∎

The space is $O(w+\log M)$, not the $O(w\log M)$ of a list storing an address with each bit. This does not imply that general circuits have small $w$.

\begin{notebookproposition} Suppose a deterministic log-space transducer transforms every circuit-value instance of length $M$ into a polynomial-length equivalent instance with a topological ordering of width $O(\log M)$. Then $\mathsf L=\mathsf P$. \end{notebookproposition}

Proof: Apply Lemma r60:stream. A requested symbol of the transducer's output can be regenerated with an output-position counter; the entire transformed instance need not be stored. Output length is polynomial, so its addresses have logarithmic length. Compose this evaluator with the log-space reductions from $\mathsf P$ [S1]. Conversely, a total deterministic log-space machine has only polynomially many configurations and cannot repeat one before halting, so $\mathsf L\subseteq\mathsf P$. ∎

Attempt to falsify an ordering-only solution.
Consider the $k\times k$ grid directed toward increasing coordinates. Put an input $x$ at $(1,1)$, copy gates on the two initial boundaries, and OR gates in the interior. Every gate computes $x$. Nevertheless every topological ordering has frontier width at least $k-1$.

An ordering of width $w$ produces bags $B_i=F_{i-1}\cup\{v_i\}$, each of size at most $w+1$. Every edge belongs to a bag: when its later endpoint is processed, the earlier endpoint is live. The bags containing a fixed vertex form an interval.

For each $(a,b)$, let $C_{a,b}$ be row $a$ together with column $b$ of the undirected grid. These sets are connected and pairwise intersect. The bags meeting a connected vertex set form an interval, because the vertex intervals overlap along the edges of a connecting tree. The intervals for all $C_{a,b}$ therefore pairwise intersect. By the finite interval Helly property, one bag meets every $C_{a,b}$. Any set of fewer than $k$ vertices misses some row and some column, and hence misses their union. That bag has at least $k$ vertices, giving $w\ge k-1$.

Thus $N=k^2$ gates can require $\Omega(\sqrt N)$ frontier width for a one-variable function with a one-gate representation. This refutes the proposed ordering-only lemma, not Proposition r60:conditional, which permits semantic changes to the circuit.

Stress test.
The ordering is supplied or generated by the hypothesized transducer; finding arbitrary topological orders is not silently treated as a log-space operation. All counters refer to encoded length, not merely the number of Boolean inputs. The grid lower bound concerns a representation, not every algorithm computing its output. A space-efficient simulator may run much longer than the original computation, so feeding its space bound into a theorem about time is invalid [E1].

The accompanying script enumerates small grid order ideals to check optimal frontier widths and compares the buffer evaluator with direct circuit evaluation. For grid sides $1,2,3,4,5$, the computed optimal widths are $0,2,3,4,5$, and all 200 seeded circuit comparisons agree. These are finite checks of implementations. The uniform storage bound and the grid obstruction are proved above, not inferred experimentally.

Outcome.
Outcome: Conditional reduction.

The argument supplies a uniform $O(w+\log M)$ evaluator and a precise sufficient semantic-normalization condition for $\mathsf L=\mathsf P$. A family of grids proves that reordering alone cannot supply that condition. No normalization of the required generality, or language separating the classes, is obtained. The storage observation is not asserted to be new to the literature.

Sources

Go to contribution →