[#P3146] Is VP equal to VNP?

Problem. Over a fixed field of characteristic zero, is every polynomial family in \(\mathrm{VNP}\) computable by polynomial-size arithmetic circuits of polynomial formal degree, equivalently is \(\mathrm{VP}=\mathrm{VNP}\)?

Permanent polynomial compared with a compact arithmetic circuit. — 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: Exponential lower bounds are known for restricted arithmetic models, while unrestricted explicit lower bounds remain far smaller. Open boundary: No superpolynomial lower bound for an explicit VNP family in general arithmetic circuits is known.

2Problem setup

Definition 1 (VP). Polynomial-degree polynomial families computed by polynomial-size arithmetic circuits.

Definition 2 (VNP). Families expressible as exponential Boolean sums of a VP family.

Remark 1. This is the algebraic analogue of P versus NP. Valiant's permanent family is VNP-complete, so polynomial-size arithmetic circuits for the permanent would imply equality.

3What counts as a solution

Construct polynomial-size circuits for every VNP family, equivalently for a standard VNP-complete family.
Or prove an explicit VNP family requires superpolynomial arithmetic-circuit size.

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: Exponential lower bounds are known for restricted arithmetic models, while unrestricted explicit lower bounds remain far smaller. Exact unresolved remainder: No superpolynomial lower bound for an explicit VNP family in general arithmetic circuits is known.^[1][2]

1Packet records

Show recorded summaries

Record	Kind	Assessment
OPEN as checked on 2026-08-01. Strongest checked neighboring result: Exponential lower bounds are known for restricted arithmetic models, while unrestricted explicit lower bounds remain far smaller. Exact unresolved remainder: No superpolynomial lower bound for an explicit VNP family in general arithmetic circuits is known.	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: Exponential lower bounds are known for restricted arithmetic models, while unrestricted explicit lower bounds remain far smaller. Exact unresolved remainder: No superpolynomial lower bound for an explicit VNP family in general arithmetic circuits is known.^[1][2] Relevance to this problem For Is VP equal to VNP?, record vp-versus-vnp-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: Exponential lower bounds are known for restricted arithmetic models, while unrestricted explicit lower bounds remain far smaller. The exact unresolved remainder is: No superpolynomial lower bound for an explicit VNP family in general arithmetic circuits is known. A complete resolution must meet the following acceptance conditions: - Construct polynomial-size circuits for every VNP family, equivalently for a standard VNP-complete family. - Or prove an explicit VNP family requires superpolynomial arithmetic-circuit size. Open full record →
Exponential lower bounds are known for restricted arithmetic models, while unrestricted explicit lower bounds remain far smaller.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 2 Exponential lower bounds are known for restricted arithmetic models, while unrestricted explicit lower bounds remain far smaller.^[1][2] Relevance to this problem For Is VP equal to VNP?, record vp-versus-vnp-claim-literature-frontier (“Strongest checked neighboring result”) records a bound, answer, status fact, or structural consequence. The record states: Exponential lower bounds are known for restricted arithmetic models, while unrestricted explicit lower bounds remain far smaller. 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 Exponential lower bounds are known for restricted arithmetic models, while unrestricted explicit lower bounds remain far smaller. This leaves the following boundary unresolved: No superpolynomial lower bound for an explicit VNP family in general arithmetic circuits is known. 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: Exponential lower bounds are known for restricted arithmetic models, while unrestricted explicit lower bounds remain far smaller. Unresolved remainder: No superpolynomial lower bound for an explicit VNP family in general arithmetic circuits is known.	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: Exponential lower bounds are known for restricted arithmetic models, while unrestricted explicit lower bounds remain far smaller. Unresolved remainder: No superpolynomial lower bound for an explicit VNP family in general arithmetic circuits is known.^[1][2] Relevance to this problem Documents why Is VP equal to VNP? 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: - VP versus VNP open 2025 survey - permanent arithmetic circuit lower bound VP VNP current The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: Exponential lower bounds are known for restricted arithmetic models, while unrestricted explicit lower bounds remain far smaller. Unresolved remainder: No superpolynomial lower bound for an explicit VNP family in general arithmetic circuits is known. Related: Claim 1 Open full record →
No superpolynomial lower bound for an explicit VNP family in general arithmetic circuits is known.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 2 No superpolynomial lower bound for an explicit VNP family in general arithmetic circuits is known. Relevance to this problem For Is VP equal to VNP?, record vp-versus-vnp-attempt-open-remainder (“Work at the unresolved boundary”) documents a concrete method, search boundary, or failed route. The record states: No superpolynomial lower bound for an explicit VNP family in general arithmetic circuits is known. 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: No superpolynomial lower bound for an explicit VNP family in general arithmetic circuits is known. A claimed resolution should satisfy every item below and preserve the statement's exact quantifiers and normalizations: - Construct polynomial-size circuits for every VNP family, equivalently for a standard VNP-complete family. - Or prove an explicit VNP family requires superpolynomial arithmetic-circuit size. 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: Exponential lower bounds are known for restricted arithmetic models, while unrestricted explicit lower bounds remain far smaller. Exact unresolved remainder: No superpolynomial lower bound for an explicit VNP family in general arithmetic circuits is known.

Equivalent-formulation queries: VP versus VNP open 2025 survey; permanent arithmetic circuit lower bound VP VNP current
Strongest checked neighboring result: Exponential lower bounds are known for restricted arithmetic models, while unrestricted explicit lower bounds remain far smaller.
Exact unresolved remainder: No superpolynomial lower bound for an explicit VNP family in general arithmetic circuits is known.

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 VP equal to VNP?

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 VP equal to VNP?.” TheoremDB. P3146. Problem statement; statement text SHA-256 be4009d8483e6fb046c60a846b9dafd89fa33167aae39e3b989de4f38af9f9f9. https://theoremdb.org/statement/?ref=P3146

BibTeX

@misc{theoremdb-problem-be4009d8483e6fb046c60a846b9dafd89fa33167aae39e3b989de4f38af9f9f9,
  title = {{Is VP equal to VNP?}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 be4009d8483e6fb046c60a846b9dafd89fa33167aae39e3b989de4f38af9f9f9},
  url = {https://theoremdb.org/statement/?ref=P3146}
}

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. L. G. Valiant, “Completeness classes in algebra”. Proceedings of the eleventh annual ACM symposium on Theory of computing - STOC '79 (1979), 249-261. DOI 10.1145/800135.804419. VP, VNP, and permanent completeness. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Introduces the classes and the complete-family framework.Also cited at L. Valiant, Completeness classes in algebra, STOC 1979. VP, VNP, and permanent completeness.Source used to assess the problem's recorded status.For Is VP equal to VNP?: This is the dated publication status for the canonical target Is VP equal to VNP?.Source named by the research packet.
ECCC TR25-083, Polynomial factorisation and algebraic complexity survey (2025). Section 4.5 and Open Problem 4.5.1. ↗journal article · secondary source · ECCC TR25-083 record checked 2026-08-01 · checked 2026-08-01Source use: original summary.Reviews current algebraic classes and records unresolved separations including VP versus VNP.Source used to assess the problem's recorded status.For Is VP equal to VNP?: Reviews current algebraic classes and records unresolved separations including VP versus VNP.

Original TheoremDB editorial statement and source synthesis; external works are used for citation only.

[#P3146] Is VP equal to VNP?

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