# P3146: Is VP equal to VNP?

- ID: `P3146`
- Reference: `vp-versus-vnp`
- Page: https://theoremdb.org/statements/P3146
- Record maturity: Reviewed problem with recorded work

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

### Context

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.

### Problem setup

- **Definition (VP).** Polynomial-degree polynomial families computed by polynomial-size arithmetic circuits.
- **Definition (VNP).** Families expressible as exponential Boolean sums of a VP family.
- **Remark.** 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.

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

## 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. [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: 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.

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.

### Background and intake notes

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

### Other known results

- **Claim 2** (supported): Exponential lower bounds are known for restricted arithmetic models, while unrestricted explicit lower bounds remain far smaller. [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: 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](#reference-1) [2](#reference-2)

### Open directions

- **Route 2** (reported): No superpolynomial lower bound for an explicit VNP family in general arithmetic circuits is known.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `vp-versus-vnp`, 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>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 https://doi.org/10.1145/800135.804419
   - Also cited at L. Valiant, Completeness classes in algebra, STOC 1979. VP, VNP, and permanent completeness
   - journal_article; primary source; checked 2026-08-01
   - Source use: original_summary
   - Introduces the classes and the complete-family framework.
   - 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.
2. <a id="reference-2"></a>ECCC TR25-083, Polynomial factorisation and algebraic complexity survey (2025). Section 4.5 and Open Problem 4.5.1 https://eccc.weizmann.ac.il/report/2025/083/
   - journal_article; secondary source; ECCC TR25-083 record checked 2026-08-01; checked 2026-08-01
   - Source 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.