# P3090: Is L equal to NL?

- ID: `P3090`
- Reference: `deterministic-logspace-versus-nondeterministic-logspace`
- Page: https://theoremdb.org/statements/P3090
- Record maturity: Reviewed problem with recorded work

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

### Context

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.

### Problem setup

- **Definition (L).** Decision problems solvable deterministically with O(log n) work space.
- **Definition (NL).** Decision problems solvable nondeterministically with O(log n) work space.
- **Remark.** Directed s-t reachability is complete for NL under logspace reductions, so a deterministic logarithmic-space algorithm for directed reachability would settle the equality.

### What 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.

## 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. [1](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (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.

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.

### Background and intake notes

- 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.
- The release review checked 2 structured sources on 2026-08-01.
- 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.

### Other known results

- **Claim 2** (supported): NL=coNL, undirected reachability is in L, and directed reachability has sublinear-space algorithms with larger time or other tradeoffs. [1](#reference-1) [2](#reference-2)

### Prior approaches

- **Route 1** (supported): 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](#reference-1) [2](#reference-2)

### Open directions

- **Route 2** (reported): Deterministic logarithmic space for directed reachability remains unknown.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `deterministic-logspace-versus-nondeterministic-logspace`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Neil Immerman, “Nondeterministic Space is Closed under Complementation”. SIAM Journal on Computing 17(5) (1988), 935-938. DOI 10.1137/0217058. NL=coNL theorem https://doi.org/10.1137/0217058
   - Also cited at N. Immerman, Nondeterministic space is closed under complementation, SIAM Journal on Computing 17 (1988). NL=coNL theorem
   - journal_article; primary source; checked 2026-08-01
   - Source use: original_summary
   - Proves the major closure theorem NL=coNL without derandomizing nondeterminism to L.
   - 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.
2. <a id="reference-2"></a>Complexity Zoo, entries L and NL. complexityzoo.net checked 2026-08-01. L and NL entries https://complexityzoo.net/Complexity_Zoo:L#nl
   - reference_database; reference source; checked 2026-08-01
   - Source 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.