[#P3090] Is L equal to NL?

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}\)?

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

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

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

Saved packet · August 1, 2026

What counts as a solution

Saved packet 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]

1Packet records

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 →
NL=coNL, undirected reachability is in L, and directed reachability has sublinear-space algorithms with larger time or other tradeoffs.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 →
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.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 →
Deterministic logarithmic space for directed reachability remains unknown.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
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 material

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 connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemIs L equal to NL?

All 3 recorded relations between these records and the problem

2See also

Multiplicative complexity of the six-bit threshold-at-least-three functiontheoretical computer science
Polynomial determinization of two-way finite automatatheoretical computer science
Logarithmic DFA separation of binary wordstheoretical computer science

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Is L equal to NL?.” TheoremDB. P3090. Problem statement; statement text SHA-256 2d5c0aefe6c8c120b5a60ebc8ac24a31a56fbbff46febb68757130795b3c5397. https://theoremdb.org/statement/?ref=P3090

BibTeX

@misc{theoremdb-problem-2d5c0aefe6c8c120b5a60ebc8ac24a31a56fbbff46febb68757130795b3c5397,
  title = {{Is L equal to NL?}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 2d5c0aefe6c8c120b5a60ebc8ac24a31a56fbbff46febb68757130795b3c5397},
  url = {https://theoremdb.org/statement/?ref=P3090}
}

Plain text: Built Markdown snapshot

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

1Lean verification

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

1Packet records

Recent contributions

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance