Algebraic complexity · arithmetic circuits · determinantal complexity · invariant theory

VP versus VNP — Permanent versus Determinant

Collaboration beta

Can the permanent be proved inherently much harder than the determinant in a way strong enough to separate the algebraic complexity classes VP and VNP?

{VP}_{ℂ} \neq {VNP}_{ℂ}, dc ({per}_{n}) \geq n^{ω (\log n)} is sufficient

Known results and sources

VP versus VNP asks whether algebraic circuits for the permanent must escape every polynomial-size construction; this route measures how large a determinant representation must become.

Research problem

Exact mathematical statement

Over $\mathbb C$ , is the algebraic complexity class $\mathrm{VP}$ strictly smaller than $\mathrm{VNP}$ ?

\mathrm{VP}_{\mathbb C}\ne\mathrm{VNP}_{\mathbb C}.

the source studies this question through the determinantal complexity $\operatorname{dc}(\operatorname{per}_n)$ , the least size $m$ of an affine linear determinant representing the $n\times n$ permanent. In the bridge used by the source, a lower bound of scale $n^{\omega(\log n)}$ is required for the full class separation unless a different direct unrestricted-circuit bridge is supplied; an exponential lower bound would be more than sufficient. The retained source explicitly says that no complete proof has been obtained.

Problem infographic

Problem at a glance

A problem-first scientific diagram compares the permanent's sum over perfect matchings with affine determinant representations of size m, distinguishes superpolynomial and superquasipolynomial targets, and marks VP not equal to VNP as open despite a strong conditional torus branch. — The packet seeks a lower bound on the determinant size needed to represent the permanent; its stable torus branch is exponential, but the asymmetric coordinate-defect branch is not yet amplified enough to separate VP from VNP.

Current mathematical picture

Where work on VP versus VNP — Permanent versus Determinant stands

Open problem

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

Useful failureSource-reported limitation

The inference is invalid: surjectivity yields one full $m^2$ -dimensional left-right orbit, but not an $n$ -dependent lower bound and not independent relabeled coordinate defects in one fixed algebra. A separate correct-strength amplification theorem is still missing. A full proof through this route needs either a theorem forcing every coordinate derivation to preserve the relation ideal or an amplification theorem turning any broken coordinate relation into at least a superquasipolynomial determinantal lower bound, or directly into an unrestricted arithmetic-circuit lower bound. A nonzero defect, a surjective conormal map, or a merely superpolynomial determinant lower bound does not close the current work's full target.

Route status · Narrowed route

Main reductionCurrent reduction

For a minimum normalized determinant representation, the current work organizes all row and column coordinate scalings into a dichotomy. If their tangents are inner, the coordinate torus lifts and a Schur-support plus prefix-weight count gives m at least 2 to the n minus 1. Otherwise, a bounded trace word or a nonzero conormal map witnesses failure of coordinate stability.

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeIndependently audit every seam in the torus-stable branch before treating its exponential lower bound as publication-ready.Task status · Ready to work on

Research-record correctionResearch-record correction

We corrected the cited passages. We clarified what the cited material supports. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

VP versus VNP — Permanent versus Determinant in numbers

3.1kretained lines of mathematical investigation3,132 in the current working snapshot

Argument development: 2,679 · 86%
Explored or eliminated routes: 111 · 4%
Computational analysis: 59 · 2%
Open obligations: 102 · 3%
Definitions and setup: 181 · 6%

9selected 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.

Proposed byLeslie G. ValiantProposed1979Status checkedAug 7, 2026

Source recordedAug 7, 2026

Recommended next task

Independently audit every seam in the torus-stable branch before treating its exponential lower bound as publication-ready.

Suggested move: Check normalized coordinate actions, finite trace bounds, algebraic-group integration, simultaneous projective lifting, finite-isogeny linearization, equivariant Schur blocks, support counting, and prefix-weight counting in the source's stated order.

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

13 selected steps

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

1 recorded

Narrowed routeSource-reported limitation

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

3 featured tasks

Independently audit every seam in the torus-stable branch before treating its exponential lower bound as publication-ready.Suggested move: Check normalized coordinate actions, finite trace bounds, algebraic-group integration, simultaneous projective lifting, finite-isogeny linearization, equivariant Schur blocks, support counting, and prefix-weight counting in the source's stated order.

Ready to work on

Resolve or quantitatively amplify vertex-flow relation grading for the full multiplication-table ideal.Suggested move: Test whether the ideal is multigraded by vertex-flow charge; if it is not, classify the shortest non-Eulerian witnesses and derive a lower bound at the required strength rather than stopping at nonvanishing.

Ready to work on

Control the genuinely nonlinear row and column marker defects at cubic and higher word length.Suggested move: Study the number, span, and support of the conormal classes induced by the 2n−1 independent coordinate derivations.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 7, 2026

Current statusOpen problem

VP versus VNP remains open, as does the superpolynomial determinantal-complexity conjecture for the permanent. Over characteristic zero the best exact benchmark lower bound remains dc(per_n) >= n^2/2, while the best general upper bound is 2^n - 1; characteristic-not-2 quadratic extensions and geometric-complexity barriers do not close the exponential gap.

[1][5][6]

External progress

What the literature has established

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

2025–2026
Authoritative summaryCurrent surveys and peer-reviewed work continue to report the general permanent determinantal-complexity frontier as a quadratic lower bound versus the 2^n - 1 upper bound.[11][12]
2019
Peer reviewedBürgisser, Ikenmeyer, and Panova proved that GCT occurrence obstructions cannot separate the relevant orbit closures, while leaving multiplicity obstructions and broader GCT approaches open.[9]
2012–2014
PreprintGrenet constructed an affine determinantal representation of the n by n permanent of size at most 2^n - 1, which remains the best general upper bound cited in 2026.[7]
2010
Peer reviewedCai, Chen, and Li extended a quadratic determinantal-complexity lower bound to every field of characteristic different from 2.[6]

Mathematical neighborhood

Related results and reusable starting points

Current focusVP versus VNP / permanent versus determinant

Equivalent formulationGeneral arithmetic-circuit complexity of the permanent

Because the permanent is VNP-complete under p-projections over the stated fields, a polynomial-size general arithmetic circuit for it would give VP = VNP; superpolynomial general circuit complexity separates the classes.

[1][10]

Weaker or relaxed formVBP or weakly-skew VP versus VNP

Polynomial-size affine determinantal representations correspond to algebraic branching programs or weakly skew circuits, so superpolynomial dc(per_n) separates VBP or VP_ws from VNP, not automatically all of VP from VNP.

[8][12]

Stronger or generalized formDeterminant versus padded-permanent orbit closures

Separating the padded-permanent orbit closure from the determinant orbit closure is the border or degeneration strengthening studied by geometric complexity theory.

[4][9]

Related problem#P-completeness of the permanent

Computing the permanent of a zero-one matrix is #P-complete in the discrete counting model. This theorem motivates the algebraic problem but is not the same as a nonuniform VP/VNP circuit separation.

[2][1]

Formal and computational footholds

Existing statements, libraries, computations, and datasets that can shorten the next serious attempt.

formal library support · source linked; not reproduced by ProofAtlasmathlib matrix permanent
Mathlib defines Matrix.permanent as the unsigned sum over permutations and proves basic structural lemmas. This is the finite polynomial, not the asymptotic complexity conjecture.
[13]
formal library support · source linked; not reproduced by ProofAtlasmathlib matrix determinant
Mathlib defines Matrix.det and develops its alternating, multiplicative, and linear-algebraic theory. It does not formalize determinant universality for weakly skew circuits in the source inspected.
[14]
formal library support · source linked; not reproduced by ProofAtlasmathlib generic multivariate-polynomial matrix
Mathlib supplies the generic matrix of distinct multivariate-polynomial variables, a useful prerequisite for statement-aligned permanent and determinant families.
[15]
software · source linked; not reproduced by ProofAtlasMacaulay2 Permanents package
The public Macaulay2 package computes permanents of concrete square matrices and can check small symbolic identities. It does not decide asymptotic determinantal complexity or VP versus VNP.
[16]

Formalization opportunities

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

Formalization targetA checked model of arithmetic circuits, circuit size and degree, nonuniform polynomial families, and the VP and VNP quantifier structure over a specified field.
Formalization targetFormal p-projections and a statement-aligned proof that the permanent family is VNP-complete under the selected conventions.
Formalization targetA formal theory of affine determinantal representations, determinantal complexity, algebraic branching programs, and their polynomial simulation equivalences.
Formalization targetExplicit field and characteristic hypotheses separating the characteristic-2 identity from the characteristic-zero and characteristic-not-2 conjectures.

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 clarified what the cited material supports. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

Research-record correctionWe corrected supporting details in the research record. 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 statements4 proposed statements3 open questions1 narrowed routes

Statements by mathematical role9 selected mapped statements

theorem candidate1 of 91
reduction1 of 91
lemma5 of 95
negative result2 of 92

Selected mathematical clusters3 mathematical clusters

Statements and reductionsClaims, implications, and derivations in the current map.17 displayed rows

retained route statementThe permanent should require determinant representations too large to arise from polynomial-size algebraic circuits.
retained route statementCurrent reductionintermediate
retained route statementClosing targetintermediate
retained route statementMinimum tuples generate the full matrix algebraintermediate
retained route statementStable torus branch is exponentialintermediate
retained route statementAsymmetric branch has one exact gateintermediate
retained route statementMultiplication tables generate every relationintermediate
retained route statementOne defect has a full bimodule orbitintermediate
retained route statementCorrect asymptotic strength remains missingintermediate
Recorded relationshipThe source material 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 work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
DerivationThe current work reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed

Open questionsSpecific obligations that remain open in the current routes.3 displayed rows

Research targetIndependently audit every seam in the torus-stable branch before treating its exponential lower bound as publication-ready.open
Research targetResolve or quantitatively amplify vertex-flow relation grading for the full multiplication-table ideal.open
Research targetControl the genuinely nonlinear row and column marker defects at cubic and higher word length.open

Explored routes and evidenceChallenges, computations, and approaches that have already narrowed the search.3 displayed rows · 1 route included

Useful failureSource-reported limitationreported failure
ComputationThe source reports that its auxiliary Python script checks the free-derivation identities, cubic oriented-defect formula, support inequality, and all-k subset-state certificates at n=5,6.The source reports exact n=5,6 SymPy checks as evidence and regression tests rather than proofs of the general theorems. the current work binds no implementation or input digest for an independent reproduction, so the computation remains source-reported and unreproduced. · reported unreproduced
Narrowed routeSource-reported limitationThe inference is invalid: surjectivity yields one full $m^2$ -dimensional left-right orbit, but not an $n$ -dependent lower bound and not independent relabeled coordinate defects in one fixed algebra. A separate correct-strength amplification theorem is still missing. A full proof through this route needs either a theorem forcing every coordinate derivation to preserve the relation ideal or an amplification theorem turning any broken coordinate relation into at least a superquasipolynomial determinantal lower bound, or directly into an unrestricted arithmetic-circuit lower bound. A nonzero defect, a surjective conormal map, or a merely superpolynomial determinant lower bound does not close the current work's full 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 bridgeIndependently audit every seam in the torus-stable branch before treating its exponential lower bound as publication-ready.

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

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointIndependently audit every seam in the torus-stable branch before treating its exponential lower bound as publication-ready.

VP versus VNP — Permanent versus Determinant · 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 the permanent be proved inherently much harder than the determinant in a way strong enough to separate the algebraic complexity classes VP and VNP?

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 references17 cited works · next context review by Nov 7, 2026

The mathematical context was checked on Aug 7, 2026. The VBP/weakly-skew relation label was corrected on Sep 11, 2026; no fresh literature search was performed. Status can be refreshed sooner after a material result or claim.

1
Completeness classes in algebraoriginal source · Leslie G. Valiant · ACM Symposium on Theory of Computing · 1979-04-30 · DOI 10.1145/800135.804419 · accessed Aug 7, 2026
2
The Complexity of Enumeration and Reliability Problemspeer reviewed result · Leslie G. Valiant · SIAM Journal on Computing · 1979-08 · DOI 10.1137/0208032 · accessed Aug 7, 2026
3
Permanent and determinantpeer reviewed result · Joachim von zur Gathen · Linear Algebra and its Applications · 1987 · DOI 10.1016/0024-3795(87)90337-5 · accessed Aug 7, 2026
4
Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problemspeer reviewed result · Ketan D. Mulmuley, Milind Sohoni · SIAM Journal on Computing · 2001 · DOI 10.1137/S009753970038715X · accessed Aug 7, 2026
5
A quadratic bound for the determinant and permanent problempeer reviewed result · Thierry Mignon, Nicolas Ressayre · International Mathematics Research Notices · 2004 · DOI 10.1155/S1073792804142566 · accessed Aug 7, 2026
6
Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristicpeer reviewed result · Jin-Yi Cai, Xi Chen, Dong Li · Computational Complexity · 2010 · DOI 10.1007/s00037-009-0284-2 · accessed Aug 7, 2026
7
An Upper Bound for the Permanent versus Determinant Problempreprint · Bruno Grenet · Author manuscript · 2012; cited as accepted 2014 · accessed Aug 7, 2026
8
On the complexity of the permanent in various computational modelspeer reviewed result · Christian Ikenmeyer, J. M. Landsberg · Journal of Pure and Applied Algebra · 2018 · ARXIV 1610.00159 · DOI 10.1016/j.jpaa.2017.02.008 · accessed Aug 7, 2026
9
No Occurrence Obstructions in Geometric Complexity Theorypeer reviewed result · Peter Bürgisser, Christian Ikenmeyer, Greta Panova · Journal of the American Mathematical Society · 2019 · ARXIV 1604.06431 · DOI 10.1090/jams/908 · accessed Aug 7, 2026
10
Completeness classes in algebraic complexity theorysurvey or monograph · Peter Bürgisser · arXiv · 2024 · ARXIV 2406.06217 · accessed Aug 7, 2026
11
Introduction to Geometric Complexity Theorysurvey or monograph · Markus Bläser, Christian Ikenmeyer · Theory of Computing Graduate Surveys · 2025-05-31 · DOI 10.4086/toc.gs.2025.010 · accessed Aug 7, 2026
12
Bounds on determinantal complexity of two types of generalized permanentspeer reviewed result · Fulvio Gesmundo, J. M. Landsberg · Theoretical Computer Science · 2026-05-02 · DOI 10.1016/j.tcs.2026.115862 · accessed Aug 7, 2026
13
Mathlib.LinearAlgebra.Matrix.Permanentformalization · mathlib contributors · Lean mathematical library · accessed Aug 7, 2026
14
Mathlib.LinearAlgebra.Matrix.Determinant.Basicformalization · mathlib contributors · Lean mathematical library · accessed Aug 7, 2026
15
Mathlib.LinearAlgebra.Matrix.MvPolynomialformalization · mathlib contributors · Lean mathematical library · accessed Aug 7, 2026
16
Permanents: computes the permanent of a square matrixsoftware or dataset · Macaulay2 contributors · Macaulay2 · accessed Aug 7, 2026
17
Complexity Zoo: V (VP and VNP entries)encyclopedia · Complexity Zoo · accessed Aug 7, 2026

Important qualifications

This successor corrects only the VBP/weakly-skew neighborhood relation label against its already-cited summary. No fresh literature search was performed; unchanged substantive claims, status dates, and source access dates retain the August 7 collection's evidence posture.
The record distinguishes VP versus VNP, VBP or weakly-skew versus VNP, and orbit-closure formulations; they must not be described as unqualified equivalents.
Bounds are field-sensitive. Characteristic 2 is exceptional because permanent equals determinant, while the cited quadratic lower bounds apply in characteristic zero or characteristic not 2 as stated.
Restricted-circuit and symmetry-respecting exponential lower bounds are not general arithmetic-circuit lower bounds and were not promoted to full-problem milestones.
The geometric-complexity occurrence-obstruction theorem blocks one proposed certificate type, not multiplicity obstructions or all geometric approaches.
No unreviewed source material, unpublished construction, or packet computation was read or evaluated.
The scoped formal-resource search verified core finite algebra but found no complete statement-aligned formalization of VP and VNP; this does not establish global nonexistence.
Macaulay2 was inspected through public documentation only and was not executed or 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