[#P3090] Is L equal to NL?

Directed reachability with logarithmic memory. — A structural automaton diagram of the statement's mathematical objects.

Problem. Can every language decided by a nondeterministic Turing machine using \(O(\log n)\) work space also be decided by a deterministic Turing machine using \(O(\log n)\) work space, equivalently is \(\mathrm L=\mathrm{NL}\)?

1Context

Known frontier: nondeterministic logarithmic space is closed under complements, undirected reachability is in L, and directed reachability has sublinear-space algorithms with larger time or other tradeoffs. Open boundary: Deterministic logarithmic space for directed reachability remains unknown.

2Problem setup

Definition 1 (L). Decision problems solvable deterministically with O(log n) work space.

Definition 2 (NL). Decision problems solvable nondeterministically with O(log n) work space.

Remark 1. Directed s-t reachability is complete for NL under logspace reductions, so a deterministic logarithmic-space algorithm for directed reachability would settle the equality.

3What counts as a solution

Give a deterministic O(log n)-space algorithm for every NL problem, equivalently directed reachability.
Or prove a language in NL requires more than logarithmic deterministic space.

1Status

Current status (Current status and exact unresolved remainder). OPEN as checked on 2026-08-01. Strongest checked neighboring result: NL=coNL, undirected reachability is in L, and directed reachability has sublinear-space algorithms with larger time or other tradeoffs. Exact unresolved remainder: Deterministic logarithmic space for directed reachability remains unknown.^[1][2]

1Records

Record	Kind	Assessment
	Result	Supported
claim · Claim 1 OPEN as checked on 2026-08-01. Strongest checked neighboring result: NL=coNL, undirected reachability is in L, and directed reachability has sublinear-space algorithms with larger time or other tradeoffs. Exact unresolved remainder: Deterministic logarithmic space for directed reachability remains unknown.^[1][2] Relevance to this problem For Is L equal to NL?, record deterministic-logspace-versus-nondeterministic-logspace-claim-status-20260801 (“Current status and exact unresolved remainder”) records a bound, answer, status fact, or structural consequence. The record states: OPEN as checked on 2026-08-01. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details The problem was checked as open on 2026-08-01. The strongest neighboring result found in the cited sources is: NL=coNL, undirected reachability is in L, and directed reachability has sublinear-space algorithms with larger time or other tradeoffs. The exact unresolved remainder is: Deterministic logarithmic space for directed reachability remains unknown. A complete resolution must meet the following acceptance conditions: - Give a deterministic O(log n)-space algorithm for every NL problem, equivalently directed reachability. - Or prove a language in NL requires more than logarithmic deterministic space. Open full record →
	Result	Supported
claim · Claim 2 NL=coNL, undirected reachability is in L, and directed reachability has sublinear-space algorithms with larger time or other tradeoffs.^[1][2] Relevance to this problem For Is L equal to NL?, record deterministic-logspace-versus-nondeterministic-logspace-claim-literature-frontier (“Strongest checked neighboring result”) records a bound, answer, status fact, or structural consequence. The record states: NL=coNL, undirected reachability is in L, and directed reachability has sublinear-space algorithms with larger time or other tradeoffs. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details NL=coNL, undirected reachability is in L, and directed reachability has sublinear-space algorithms with larger time or other tradeoffs. This leaves the following boundary unresolved: Deterministic logarithmic space for directed reachability remains unknown. The distinction is retained here so a restricted theorem, finite computation, or neighboring case is not presented as a solution of the full target. Related: Claim 1 Open full record →
	Trace	Supported
attempt · Route 1 The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: NL=coNL, undirected reachability is in L, and directed reachability has sublinear-space algorithms with larger time or other tradeoffs. Unresolved remainder: Deterministic logarithmic space for directed reachability remains unknown.^[1][2] Relevance to this problem Documents why Is L equal to NL? was treated as a distinct open target on 2026-08-01. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope No narrower scope recorded Sources Reference 1, Reference 2 What happened The audit ran on 2026-08-01 across the cited primary literature and problem collections, Crossref, arXiv, and stable publisher records, TheoremDB published, prospecting, packet, formal, and retired corpus. It checked the exact statement, its named or normalized variants, recent status evidence, and the controlled TheoremDB corpus. Queries included: - L versus NL open problem current - directed reachability deterministic logspace open The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: NL=coNL, undirected reachability is in L, and directed reachability has sublinear-space algorithms with larger time or other tradeoffs. Unresolved remainder: Deterministic logarithmic space for directed reachability remains unknown. Related: Claim 1 Open full record →
	Trace	Reported
attempt · Route 2 Deterministic logarithmic space for directed reachability remains unknown. Relevance to this problem For Is L equal to NL?, record deterministic-logspace-versus-nondeterministic-logspace-attempt-open-remainder (“Work at the unresolved boundary”) documents a concrete method, search boundary, or failed route. The record states: Deterministic logarithmic space for directed reachability remains unknown. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded What happened Research should address this boundary directly: Deterministic logarithmic space for directed reachability remains unknown. A claimed resolution should satisfy every item below and preserve the statement's exact quantifiers and normalizations: - Give a deterministic O(log n)-space algorithm for every NL problem, equivalently directed reachability. - Or prove a language in NL requires more than logarithmic deterministic space. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. OPEN as checked on 2026-08-01. Strongest checked neighboring result: NL=coNL, undirected reachability is in L, and directed reachability has sublinear-space algorithms with larger time or other tradeoffs. Exact unresolved remainder: Deterministic logarithmic space for directed reachability remains unknown.

Equivalent-formulation queries: L versus NL open problem current; directed reachability deterministic logspace open
Strongest checked neighboring result: NL=coNL, undirected reachability is in L, and directed reachability has sublinear-space algorithms with larger time or other tradeoffs.
Exact unresolved remainder: Deterministic logarithmic space for directed reachability remains unknown.

How the 4 records connectTyped relations and evidence flow

ProblemIs L equal to NL?

Claim 1Current status and exact unresolved remainderin this packetSupported
Route 1Dated source and duplicate auditchecksSupported
Claim 2Strongest checked neighboring resultinformsSupported
Route 2Work at the unresolved boundaryaddressesReported

2See also

Is VP equal to VNP?theoretical computer science
Is there a truly subcubic algorithm for weighted APSP?theoretical computer science
Strong Exponential Time Hypothesistheoretical computer science

How to cite

TheoremDB contributors, “Is L equal to NL?,” TheoremDB research memory, snapshot of August 1, 2026. https://theoremdb.org/statements/deterministic-logspace-versus-nondeterministic-logspace

This page as plain text: deterministic-logspace-versus-nondeterministic-logspace.md

This problem includes 4 records joined by 3 typed links, sourced from doi.org^[1], current as of August 1, 2026.

1References

Packet source. Neil Immerman, “Nondeterministic Space is Closed under Complementation”. SIAM Journal on Computing 17(5) (1988), 935-938. DOI 10.1137/0217058. NL=coNL theorem. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Proves the major closure theorem NL=coNL without derandomizing nondeterminism to L.Also cited at N. Immerman, Nondeterministic space is closed under complementation, SIAM Journal on Computing 17 (1988). NL=coNL theorem.Source used to assess the problem's recorded status.For Is L equal to NL?: This is the dated publication status for the canonical target Is L equal to NL?.Source named by the research packet.
Complexity Zoo, entries L and NL. complexityzoo.net checked 2026-08-01. L and NL entries. ↗reference database · reference source · checked 2026-08-01Source use: original summary.Records containments, complete problems, and the unresolved equality.Source used to assess the problem's recorded status.For Is L equal to NL?: Records containments, complete problems, and the unresolved equality.

Original TheoremDB editorial statement and source synthesis; external works are used for citation only.

[#P3090] Is L equal to NL?

1Context

2Problem setup

3What counts as a solution

1Status

1Records

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Records

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance