ProofAtlas

Computational complexity · parallel computation · circuit complexity

P versus NC

Collaboration beta

P captures efficient sequential computation; NC captures computation that can be organized into polynomially many parallel operations and polylogarithmic depth. Whether the two classes are equal remains open.

P=?NC
Known results and sources
Editorial comparison of a polynomial sequential computation and a bounded-fan-in polylog-depth uniform circuit, centered on the open equality P=NC.
Whether every polynomial-time computation admits efficient uniform parallel circuits remains open.

Research problem

Exact mathematical statement

Let

NC=⋃k≥1NCk,\mathrm{NC}=\bigcup_{k\ge1}\mathrm{NC}^k,

where NCk\mathrm{NC}^k consists of languages decided by logspace-uniform, polynomial-size, bounded-fan-in Boolean circuit families of depth O(logkn)O(\log^k n). Determine whether

P=NC.\mathrm P=\mathrm{NC}.

The retained source reports neither equality nor separation.

Problem infographic

Problem at a glance

Problem-first P versus NC explainer defining the classes, the Circuit Value equivalence, and the source’s unconstructed closed-descriptor target without depicting a proof.
The packet distinguishes closed state-independent summaries from open state transducers and proposes a finite-horizon descriptor target, but obtains neither equality nor separation.

Current mathematical picture

Where work on P versus NC stands

Open problem

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureOpen transducer balancing

Raw syntax has cheap composition yet leaves the P-complete evaluator inside the decoder. A finite-horizon, output-sensitive closed descriptor with controlled total construction and application ranks remains the primary constructive target.

Route status · Narrowed route
Main reductionCircuit Value is the P-complete test

The source records the standard equivalence P=NC iff Circuit Value lies in NC.

Evidence posture · Source-reported route statement · dependencies incomplete
Priority open bridgeConstruct a nontrivial closed descriptor.Task status · Ready to work on
Research-record correctionResearch-record correction

We 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 unchanged

Work mapped so far

P versus NC in numbers

1.6kretained lines of mathematical investigation1,625 in the current working snapshot
Argument development
1,296 · 80%
Explored or eliminated routes
58 · 4%
Computational analysis
85 · 5%
Open obligations
69 · 4%
Definitions and setup
117 · 7%
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.

Status checkedAug 14, 2026
Source recordedAug 14, 2026

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

11 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

11 selected steps

Scroll horizontally to explore the route

Working route overview for P versus NCA selected map of recorded claims, active routes, useful failures, open questions, and their explicit relationships. Search, filter, zoom, or pan within this page.Can every polynomial-time computation be efficiently parallelized? — Depends on missing premiseCan every polynomial-timecomputation be efficientlyparallelized?Circuit Value is the P-complete test — Depends on missing premiseCircuit Value is theP-complete testCurrent reduction — Depends on missing premiseCurrent reductionClosing target — Depends on missing premiseClosing targetCompiler characterization is not a resolution — Depends on missing premiseCompiler characterization isnot a resolutionOpen transducers are not closed summaries — Depends on missing premiseOpen transducers are notclosed summariesSmall-width census is finite only — Depends on missing premiseSmall-width census is finiteonlyOpen transducer balancing — stoppedOpen transducer balancingConstruct a nontrivial closed descriptor. — OpenConstruct a nontrivialclosed descriptor.Prove a robust restricted tradeoff. — OpenProve a robust restrictedtradeoff.Audit the compiler characterization. — OpenAudit the compilercharacterization.
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

1 recorded
Narrowed routeOpen transducer balancing

Raw syntax has cheap composition yet leaves the P-complete evaluator inside the decoder. A finite-horizon, output-sensitive closed descriptor with controlled total construction and application ranks remains the primary constructive target.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

3 featured tasks
01
Construct a nontrivial closed descriptor.Suggested move: For a concrete finite-horizon universal reversible segment grammar, define state-independent descriptors and record exact merge, application, weighted-size, rank, and uniformity costs.
Ready to work on
02
Prove a robust restricted tradeoff.Suggested move: Establish a size-versus-application or cumulative-rank lower bound for a descriptor grammar broad enough to survive auxiliary definitions and noncanonical encodings.
Ready to work on
03
Audit the compiler characterization.Suggested move: Independently check shared-DAG, rank-zero, charged-constant, multi-output, valid-subcube, and logspace-uniform indexing edge cases before using the custom rank framework.
Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 14, 2026
Current statusOpen problem

NC is contained in P, and whether NC=P remains open. Circuit Value is P-complete under logspace reductions, so placing it in NC would imply P=NC; no reviewed official source reports such an algorithm or a separation.

[2][3]
External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

  1. Authoritative summaryCornell’s parallel algorithms notes define NC by uniform polynomial-size polylog-depth circuits and state that P=NC iff a P-complete problem such as Circuit Value lies in NC.[2]
  2. Peer reviewedLadner proved Circuit Value logspace-complete for P, furnishing the canonical P-complete evaluator used in the P-versus-NC equivalence.[1]
3 cited sources2 related results or reductionsReferences

Mathematical neighborhood

Related results and reusable starting points

Current focusP versus NC
Equivalent formulationCircuit Value in NC

Because Circuit Value is P-complete under logspace reductions, Circuit Value in NC is equivalent to P=NC under the standard uniform setup.

[1][2]
Related problemP-complete problems

P-completeness identifies problems believed resistant to efficient parallelization, but P-completeness alone is conditional evidence and not a separation theorem.

[2]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

  • Formalization targetA formal uniform-circuit definition of NC and simulation proof establishing NC⊆P.
  • Formalization targetFormal logspace-reduction and P-completeness infrastructure for Circuit Value.
  • Formalization targetA machine-checked asymptotic compiler or lower bound sufficient for equality or separation.

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.

Corrected the research recordCorrection note

Correction details
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.

Corrected the research recordCorrection note

Correction details

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
Statements by mathematical role7 selected mapped statements
  • theorem candidate1 of 71
  • reduction2 of 72
  • lemma1 of 71
  • negative result2 of 72
  • computational claim1 of 71
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 statementCan every polynomial-time computation be efficiently parallelized?
  • retained route statementCurrent reductionintermediate
  • retained route statementClosing targetintermediate
  • retained route statementCompiler characterization is not a resolutionintermediate
  • retained route statementCircuit Value is the P-complete testintermediate
  • retained route statementOpen transducers are not closed summariesintermediate
  • retained route statementSmall-width census is finite onlyintermediate
  • 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 failureOpen transducer balancingreported failure
  • Research targetConstruct a nontrivial closed descriptor.open
  • Research targetProve a robust restricted tradeoff.open
  • Research targetAudit the compiler characterization.open
  • Research targetExact P versus NC conventionsuperseded
  • Research targetEquality or separation remains opensuperseded
  • Narrowed routeOpen transducer balancingRaw syntax has cheap composition yet leaves the P-complete evaluator inside the decoder. A finite-horizon, output-sensitive closed descriptor with controlled total construction and application ranks remains the primary constructive target.
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

Priority open bridgeConstruct a nontrivial closed descriptor.

1 approach has already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

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.

Read-only beta · actions unavailable
Prepared starting pointConstruct a nontrivial closed descriptor.

P versus NC · 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

P captures efficient sequential computation; NC captures computation that can be organized into polynomially many parallel operations and polylogarithmic depth. Whether the two classes are equal remains open.

  • 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.

  1. 1
    The circuit value problem is log space complete for Poriginal source · Richard E. Ladner · ACM SIGACT News · 1975-01 · DOI 10.1145/990518.990519 · accessed Aug 14, 2026
  2. 2
    Parallel Algorithms and NCauthoritative webpage · Cornell University Department of Computer Science · 2022 · accessed Aug 14, 2026
  3. 3
    Complexity Zoo: Pmaintained problem list · Complexity Zoo · accessed Aug 14, 2026

Important qualifications

  • The collection uses official university notes and a maintained expert reference for current class relations; it is not an exhaustive circuit-complexity survey.
  • Circuit Value P-completeness is historical primary evidence but does not by itself resolve P versus NC.
  • No claimed lower bound, compiler, or experimental result from the unreviewed source material was externally validated.

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

Expanded visual

Open original image