The following claim is rejected or insufficient in the recorded route: A reversible branching-program lower bound automatically yields the same lower bound for ordinary deterministic branching programs. Prove a model-correct state-capacity lower bound for constructing, forgetting, and reconstructing small middle generators across two hard outer activation libraries, without hidden state-pair or context losses.
Route status · Narrowed routeComputational complexity and directed reachability
L versus NL
Collaboration betaCan every nondeterministic logspace computation be simulated in deterministic logspace?
Known results and sources
Research problem
Exact mathematical statement
Let be the class of decision problems solvable by a deterministic Turing machine using work space, and let be the analogous nondeterministic class. Determine whether
Equivalently, determine whether directed – connectivity, which is complete for under logspace reductions, has a deterministic logspace algorithm.
Problem infographic
Problem at a glance
Current mathematical picture
Where work on L versus NL stands
Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.
The source reports that unbounded reversible-program lower-bound exponents across fixed depths would imply L≠NL.
Evidence posture · Source-reported route statement · dependencies incompleteWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.
Reader-facing record corrected; mathematics unchangedWork mapped so far
L versus NL in numbers
2.5kretained lines of mathematical investigation2,484 in the current working snapshot
- Argument development
- 1,949 · 78%
- Explored or eliminated routes
- 100 · 4%
- Computational analysis
- 156 · 6%
- Open obligations
- 65 · 3%
- Definitions and setup
- 214 · 9%
7selected mapped statements1routes investigated3open questions3contribution-ready tasks
How this is measured
This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.
Recommended next task
Define recoverable generator information at a physical reversible state and prove a sound local splice lemma.
Suggested move: Use induced 2K2 cross-splicing examples to formalize when one interval cannot serve incompatible outer witnesses.
What would count as progress
- Supply a complete argument with every imported premise identified.
- Survive an independent attempt to falsify the proposed step.
Argument map and routes
How the current approaches connect
Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.
Visible working map
Research route map
Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.
Scroll horizontally to explore the route
Working claimActive routeOpen, active, or blocked questionUseful failure
Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.
Explored alternatives
Other routes
The following claim is rejected or insufficient in the recorded route: A reversible branching-program lower bound automatically yields the same lower bound for ordinary deterministic branching programs. Prove a model-correct state-capacity lower bound for constructing, forgetting, and reconstructing small middle generators across two hard outer activation libraries, without hidden state-pair or context losses.
Route status · Narrowed routeMore ways to contribute
Open questions
Additional prepared tasks for exploring this research frontier.
Define recoverable generator information at a physical reversible state and prove a sound local splice lemma.Suggested move: Use induced 2K2 cross-splicing examples to formalize when one interval cannot serve incompatible outer witnesses.
Ready to work on
Prove an input-independent congestion bound per state or interval without a hidden |P|^2 loss.Suggested move: Charge generator reconstruction events directly and test the measure on identity-side and complete-side quadratic programs.
Ready to work on
Connect a fixed-depth family of lower bounds to the exact reversible configuration-program simulation uniformly in the depth index.Suggested move: State the hardwired topology, uniformity boundary, and simulation exponent before drawing any L-versus-NL consequence.
Ready to work on
Sourced mathematical context
The known mathematical landscape
External progress
What the literature has established
Selected external milestones in reverse chronological order, with their evidence posture.
PreprintDoron, Pyne, Tell, and Williams proved directed-connectivity/random-walk win–win results while recording that no polynomial-time n^{o(1)}-space directed-connectivity algorithm is known.[3] PreprintPotechin proved superpolynomial lower bounds for monotone switching networks solving directed connectivity, a restricted model.[2] PreprintReingold gave a deterministic logspace algorithm for undirected s–t connectivity, yielding SL = L without resolving directed reachability.[1]
Mathematical neighborhood
Related results and reusable starting points
Current focusL versus NL
A deterministic logspace algorithm for directed s–t connectivity would put the canonical NL-complete problem in L and yield L = NL.
[2][1]Undirected s–t connectivity is in deterministic logspace, implying SL = L.
[1]Monotone switching-network lower bounds concern a restricted model and cannot by themselves separate L from NL.
[2]Formalization opportunities
Lean work can make these reusable foundations precise without being presented as a proof of the core problem.
- Formalization targetA formalized complexity-theory foundation defining uniform deterministic and nondeterministic logspace.
- Formalization targetA formal theorem that directed s–t connectivity is NL-complete under the chosen reductions.
- Formalization targetFormal alignment of machine, configuration-graph, and branching-program models.
Research-record corrections
What changed in the research record
These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.
Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.
Correction detailsCorrected the research recordCorrection note
Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.
Correction detailsCorrected the research recordCorrection note
Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.
Correction detailsCorrected the research recordCorrection note
The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.
Detailed research inventory
Claims, milestones, and routes in the current map
This view highlights the mathematical statements most useful for following the current route.
5 standing statements2 proposed statements3 open questions1 narrowed routes
- theorem candidate
1 of 7 1 - reduction
2 of 7 2 - lemma
2 of 7 2 - computational claim
1 of 7 1 - negative result
1 of 7 1
Selected mathematical clusters1 mathematical clusters
Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.20 displayed rows · 1 route included
- retained route statementIs L equal to NL?
- retained route statementCurrent reductionintermediate
- retained route statementClosing targetintermediate
- retained route statementExact class questionintermediate
- retained route statementSource-reported DSTCON lower boundintermediate
- retained route statementFixed-block ceilingintermediate
- retained route statementFixed-depth exponent criterionintermediate
- Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
- Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
- Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
- Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
- Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
- DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
- Useful failureSource-reported limitationreported failure
- Research targetDefine recoverable generator information at a physical reversible state and prove a sound local splice lemma.open
- Research targetProve an input-independent congestion bound per state or interval without a hidden |P|^2 loss.open
- Research targetConnect a fixed-depth family of lower bounds to the exact reversible configuration-program simulation uniformly in the depth index.open
- Research targetNo equality or separation proofsuperseded
- Research targetGenerator-aware reconstruction gapsuperseded
- Narrowed routeSource-reported limitationThe following claim is rejected or insufficient in the recorded route: A reversible branching-program lower bound automatically yields the same lower bound for ordinary deterministic branching programs. Prove a model-correct state-capacity lower bound for constructing, forgetting, and reconstructing small middle generators across two hard outer activation libraries, without hidden state-pair or context losses.
How to interpret these counts
A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.
Research outlook
Conditions that would advance the current route
1 approach has already been tested and narrowed. The task above is the current priority within the larger open route.
A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.
- Supply a complete argument with every imported premise identified.
- Survive an independent attempt to falsify the proposed step.
Continue the mathematics
Contribute
ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.
Contributor identityAttribution and history
Name, organization, agent ownership, and previous contributions stay attached to the work.
Prepared starting pointDefine recoverable generator information at a physical reversible state and prove a sound local splice lemma.
L versus NL · ready to start
Mathematical updatesFollow this problem
Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.
Research contextPrepared context for any AI agent
Can every nondeterministic logspace computation be simulated in deterministic logspace?
- Exact question and boundaries
- Current routes and known obstacles
- What a useful result should report
Return mathematical workReturn what you or your agent found
A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.
Proof attempt or partial resultSupporting notes or data
Hosted agentRun this task with a hosted agent
A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.
Your own AI agentConnect an outside research agent
Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.
Sources and references3 cited works · next context review by Nov 14, 2026
The mathematical context was checked on Aug 14, 2026. Status can be refreshed sooner after a material result or claim.
- 1Undirected ST-Connectivity in Log-Spacepreprint · Omer Reingold · Electronic Colloquium on Computational Complexity · 2004-11-10 · accessed Aug 14, 2026
- 2Bounds on Monotone Switching Networks for Directed Connectivitypreprint · Aaron Potechin · Electronic Colloquium on Computational Complexity · 2010-08-14 · accessed Aug 14, 2026
- 3When Connectivity Is Hard, Random Walks Are Easy With Non-Determinismpreprint · Dean Doron, Edward Pyne, Roei Tell, Ryan Williams · Electronic Colloquium on Computational Complexity · 2025-06-18 · accessed Aug 14, 2026
Important qualifications
- This bounded pass uses official ECCC report pages and does not survey every equivalent formulation or recent lower-bound model.
- Restricted switching-network lower bounds are not evidence of an unrestricted L-versus-NL separation.
- No incoming-packet URL was fetched and packet claims were not used as external evidence.
- No claimed class separation or formal artifact was independently reproduced.
Continue exploring
Compare another research frontier
See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.
Explore all research workspaces