pith. sign in

arxiv: 2605.09551 · v1 · submitted 2026-05-10 · 💻 cs.CC

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings

Balagopal Komarath , Harshil Mittal , Jayalal Sarma This is my paper

Pith reviewed 2026-05-12 03:05 UTC · model grok-4.3

classification 💻 cs.CC
keywords min-plus semiringsVP and VNPalgebraic branching programsdichotomy theoremconstant-width programsoptimization complexitycertificate complementationhypercube sums
0
0 comments X

The pith

Over min-plus semirings, VNP equals VP if certificates complement only logarithmically many values but separates when super-logarithmic complements are used, and constant-width ABPs reach full power at width 3.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies polynomials over min-plus semirings that model pure optimization algorithms using only minimum and addition operations. It defines a nondeterministic class VNP by allowing free complementation of values inside efficiently verifiable certificates for problems such as minimum-weight matchings and cycles. The central result is a dichotomy: when at most logarithmically many values are complemented, this VNP coincides with the deterministic VP class; when super-logarithmically many values are complemented, the classes are distinct. Separately, algebraic branching programs of constant width cannot compute even minimum-weight 2-edge-matching at width 2, yet width 3 suffices to compute every function in the class and to simulate constant-depth formulas efficiently.

Core claim

The authors prove a dichotomy theorem for VNP over min-plus semirings: if certificates complement at most a logarithmic number of values, then VNP equals VP; if super-logarithmically many values are complemented, then VNP is strictly larger than VP. They also show that constant-width algebraic branching programs over these semirings cannot compute the minimum-weight 2-edge-matching polynomial with width 2, but programs of width 3 can compute every function in the class and efficiently simulate constant-depth formulas. Finally, they establish that taking the exponential hypercube minimum-sum over even weak models such as width-2 ABPs or products of linear forms yields the full VNP class.

What carries the argument

Limited complementation of values inside certificates for the VNP definition over min-plus semirings, together with constant-width algebraic branching programs viewed as register-restricted incremental dynamic programs.

If this is right

  • Minimum-weight perfect matchings and Hamiltonian cycles belong to VNP over min-plus semirings once suitable certificates with complements are allowed.
  • Constant-depth formulas over min-plus semirings convert efficiently into constant-width algebraic branching programs.
  • The exponential hypercube minimum over width-2 ABPs or over products of linear forms already captures the full VNP class.
  • Minimum-weight 2-edge-matching requires algebraic branching program width at least 3, marking a sharp threshold in the number of registers needed for dynamic programs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The precise count of complemented values may act as a knob that separates deterministic from nondeterministic power for a broad range of optimization tasks.
  • Practical register-limited dynamic programming algorithms could face an abrupt jump in solvable problems once three registers become available.
  • Analogous complementation thresholds could be defined and studied for other semirings to classify additional families of optimization problems.
  • One could check whether concrete optimization instances arising in applications naturally require super-logarithmic complements in their shortest certificates.

Load-bearing premise

The premise that controlled free complementation of certificate values is the right notion of nondeterminism for optimization problems modeled by min-plus semirings.

What would settle it

An explicit polynomial that requires super-logarithmic complements to be placed in VNP but cannot be computed with only logarithmic complements, or an explicit width-2 algebraic branching program that computes the minimum-weight 2-edge-matching polynomial.

read the original abstract

Arithmetic circuit complexity studies the complexity of computing polynomials using only arithmetic operations such as addition, multiplication, subtraction, and division. Polynomials over rings of integers model counting problems. Similarly, polynomials over semirings such as tropical semirings model optimization problems. Circuits over semirings then model so called pure algorithms, algorithms that only use the operations in the semiring. In this paper, we do a complexity-theoretic study of the power and limitations of circuits (which represent dynamic programs) over semirings: i) We define $\mathsf{VNP}$ over min-plus semirings, which can faithfully represent problems such as computing min-weight perfect matchings and min-weight Hamiltonian cycles where we have efficiently verifiable certificates. Unlike over rings, we complement the values in the certificate for free as complementation is impossible over min-plus semirings. We prove a dichotomy theorem that states that if we only complement logarithmically many values, this class is same as $\mathsf{VP}$ over min-plus semirings. If we complement super-logarithmically many values, then $\mathsf{VNP} \neq \mathsf{VP}$. ii) We consider constant-width ABPs (which are also called incremental dynamic programs that are restricted to use only a constant number of registers) and show that even simple problems like computing the min-weight $2$-edge-matching is impossible with width $2$ (or $2$ registers). However, with width $3$ (or $3$ registers), such programs can compute everything. More generally, we show that constant-depth formulas are efficiently simulated by constant-width ABPs. iii) We show that an exponential hypercube sum (min in the semiring) over even provably weak models such as width-$2$ ABPs and products of linear forms are the same as $\mathsf{VNP}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper defines VP and VNP over min-plus semirings to model pure optimization algorithms, with VNP allowing free complementation of certificate values. It proves a dichotomy: VNP equals VP when O(log n) values are complemented but VNP properly contains VP for superlogarithmic complements. It shows width-2 ABPs cannot compute min-weight 2-edge-matching while width-3 ABPs simulate all problems and constant-depth formulas; it also equates exponential hypercube min-sums over width-2 ABPs and linear-form products to VNP.

Significance. If correct, the work supplies a precise threshold for when certificate complementation collapses VNP to VP in semiring models of optimization, plus concrete separations and simulations for constant-width ABPs that clarify the power of limited-register dynamic programs. The hypercube-sum equivalence strengthens the VNP definition. These are novel contributions to algebraic complexity outside rings, with potential to organize results on tropical and min-plus circuits.

major comments (2)
  1. [Dichotomy theorem proof] Dichotomy theorem (proof of VNP=VP direction): the argument that any poly-size VNP circuit with O(log n) complements converts to a poly-size VP circuit must explicitly rule out size blowup from enumerating the poly(n) complementation patterns. Under min-plus operations, aggregating 2^{O(log n)} cases via repeated min or plus does not obviously remain polynomial; the manuscript should supply the simulation construction or structural property of certificates that avoids this cost.
  2. [Constant-width ABP results] Constant-width ABP section: the claim that width-3 ABPs 'can compute everything' is load-bearing for the width threshold result but requires a precise statement of the target class (e.g., all degree-n polynomials in VNP or all min-weight problems with poly-size certificates). Without this, it is impossible to verify whether the width-3 simulation is complete or only covers specific problems such as matchings.
minor comments (2)
  1. [Introduction] The definition of VNP over min-plus (including how certificates and free complementation are formalized) should appear in the introduction before the dichotomy statement, to make the model self-contained.
  2. [Preliminaries] Notation for the min-plus semiring operations and the precise meaning of 'complement logarithmically many values' should be fixed early and used consistently in all theorems.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. The positive assessment of the significance is appreciated. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Dichotomy theorem proof] Dichotomy theorem (proof of VNP=VP direction): the argument that any poly-size VNP circuit with O(log n) complements converts to a poly-size VP circuit must explicitly rule out size blowup from enumerating the poly(n) complementation patterns. Under min-plus operations, aggregating 2^{O(log n)} cases via repeated min or plus does not obviously remain polynomial; the manuscript should supply the simulation construction or structural property of certificates that avoids this cost.

    Authors: We thank the referee for highlighting this point. The current proof sketch uses the polynomial number of patterns (2^{O(log n)}) together with the polynomial-size certificates to argue that a direct enumeration can be simulated by a poly-size circuit, but we agree that the aggregation step under min and plus requires an explicit construction to confirm no superpolynomial blowup occurs. We will add a detailed simulation in the revised manuscript: the complemented values are treated as independent choices, and the min over all patterns is realized by a layered circuit that computes partial minima over subsets of patterns using a binary-tree aggregation of min gates (each of constant fan-in), which keeps the total size polynomial because the depth is logarithmic in the number of patterns and the width is bounded by the original circuit size. revision: yes

  2. Referee: [Constant-width ABP results] Constant-width ABP section: the claim that width-3 ABPs 'can compute everything' is load-bearing for the width threshold result but requires a precise statement of the target class (e.g., all degree-n polynomials in VNP or all min-weight problems with poly-size certificates). Without this, it is impossible to verify whether the width-3 simulation is complete or only covers specific problems such as matchings.

    Authors: We agree that the phrasing 'can compute everything' should be made precise. In the manuscript this means that width-3 ABPs can simulate every polynomial-size VNP circuit over the min-plus semiring (i.e., every min-weight optimization problem admitting a polynomial-size certificate). The simulation proceeds by first converting the VNP circuit to a constant-depth formula (via the hypercube-sum equivalence shown later) and then simulating that formula with a width-3 ABP; the 2-edge-matching lower bound for width 2 then yields the separation. We will revise the statement of the theorem and the surrounding text to explicitly name the target class as the full VNP and to reference the simulation construction. revision: yes

Circularity Check

0 steps flagged

No circularity: new definitions and dichotomy rest on independent structural arguments

full rationale

The paper introduces fresh definitions of VP and VNP over min-plus semirings (allowing free complementation in certificates) and derives the dichotomy theorem directly from the number of complemented values (logarithmic vs. superlogarithmic). Constant-width ABP results and the hypercube-sum equivalence follow from explicit simulations and width bounds without reducing any central claim to a fitted parameter, self-citation chain, or definitional tautology. All steps are self-contained against the semiring operations and do not invoke prior author results as load-bearing uniqueness theorems.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claims rest on standard algebraic properties of semirings and new definitions of complexity classes without additional free parameters or invented physical entities.

axioms (1)
  • standard math The min-plus semiring is a commutative semiring with min as addition and + as multiplication, satisfying the usual axioms.
    Fundamental to defining circuits and ABPs over it.
invented entities (1)
  • VNP over min-plus semirings no independent evidence
    purpose: To model optimization problems with verifiable certificates using min-plus operations.
    Newly introduced to extend ring-based complexity to semirings.

pith-pipeline@v0.9.0 · 5648 in / 1602 out tokens · 47633 ms · 2026-05-12T03:05:32.604961+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    Arithmetic Circuits

    Vollmer, Heribert. Arithmetic Circuits. Introduction to Circuit Complexity: A Uniform Approach. 1999

    work page 1999

  2. [2]

    arXiv preprint arXiv:2512.23121 , year=

    Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width , author=. arXiv preprint arXiv:2512.23121 , year=

    work page arXiv

  3. [3]

    SIAM Journal on Computing , volume=

    Fast Parallel Computation of Polynomials Using Few Processors , author=. SIAM Journal on Computing , volume=. 1983 , publisher=

    work page 1983

  4. [4]

    Malod, Guillaume , year=. Polyn

    work page

  5. [5]

    Information and Computation , volume=

    Non-uniform automata over groups , author=. Information and Computation , volume=. 1990 , publisher=

    work page 1990

  6. [6]

    2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Waring rank, parameterized and exact algorithms , author=. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2019 , organization=

    work page 2019

  7. [7]

    Journal of Automata, Languages and Combinatorics , volume=

    The computing power of programs over finite monoids , author=. Journal of Automata, Languages and Combinatorics , volume=. 2001 , publisher=

    work page 2001

  8. [8]

    Proceedings of the eighteenth annual ACM symposium on Theory of computing , pages=

    Bounded-width polynomial-size branching programs recognize exactly those languages in NC , author=. Proceedings of the eighteenth annual ACM symposium on Theory of computing , pages=

    work page

  9. [9]

    Proceedings of the London Mathematical Society Symposium on Boolean Function Complexity , pages=

    Monotone complexity , author=. Proceedings of the London Mathematical Society Symposium on Boolean Function Complexity , pages=

    work page

  10. [10]

    International Journal of Advances in Engineering Sciences and Applied Mathematics , volume=

    Shortest path length with bounded-alternation (min,+) formulas , author=. International Journal of Advances in Engineering Sciences and Applied Mathematics , volume=. 2019 , publisher=

    work page 2019

  11. [11]

    Theory of Computing , volume=

    Monotone Projection Lower Bounds from Extended Formulation Lower Bounds , author=. Theory of Computing , volume=

    work page

  12. [12]

    Journal of the ACM (JACM) , volume=

    On algebraic branching programs of small width , author=. Journal of the ACM (JACM) , volume=. 2018 , publisher=

    work page 2018

  13. [13]

    Notes on Tropical Language and Applications , howpublished =

    work page

  14. [14]

    Proceedings of the eleventh annual ACM symposium on Theory of computing , pages=

    Completeness classes in algebra , author=. Proceedings of the eleventh annual ACM symposium on Theory of computing , pages=

    work page

  15. [15]

    Journal of the ACM (JACM) , volume=

    The parallel evaluation of general arithmetic expressions , author=. Journal of the ACM (JACM) , volume=. 1974 , publisher=

    work page 1974

  16. [16]

    Theory of Computing Systems , volume=

    Lower bounds for tropical circuits and dynamic programs , author=. Theory of Computing Systems , volume=. 2015 , publisher=

    work page 2015

  17. [17]

    On the optimality of

    Jukna, Stasys and Schnitger, Georg , journal=. On the optimality of. 2016 , publisher=

    work page 2016

  18. [18]

    Journal of the ACM (JACM) , volume=

    Some exact complexity results for straight-line computations over semirings , author=. Journal of the ACM (JACM) , volume=. 1982 , publisher=

    work page 1982

  19. [19]

    Discrete mathematics , volume=

    Otakar Boruvka on minimum spanning tree problem Translation of both the 1926 papers, comments, history , author=. Discrete mathematics , volume=. 2001 , publisher=

    work page 1926

  20. [20]

    Proceedings of the American Mathematical society , volume=

    On the shortest spanning subtree of a graph and the traveling salesman problem , author=. Proceedings of the American Mathematical society , volume=. 1956 , publisher=

    work page 1956

  21. [21]

    The Bell System Technical Journal , volume=

    Shortest connection networks and some generalizations , author=. The Bell System Technical Journal , volume=. 1957 , publisher=

    work page 1957

  22. [22]

    Github survey , volume=

    A survey of lower bounds in arithmetic circuit complexity , author=. Github survey , volume=

    work page

  23. [23]

    Characterizing

    Malod, Guillaume and Portier, Natacha , journal=. Characterizing. 2008 , publisher=

    work page 2008

  24. [24]

    Quarterly of applied mathematics , volume=

    On a routing problem , author=. Quarterly of applied mathematics , volume=

    work page

  25. [25]

    Kolmogorov, Vladimir , journal=. Blossom. 2009 , publisher=

    work page 2009

  26. [26]

    Proceedings of the twentieth annual ACM symposium on Theory of computing , pages=

    Computing algebraic formulas with a constant number of registers , author=. Proceedings of the twentieth annual ACM symposium on Theory of computing , pages=

    work page

  27. [27]

    computational complexity , volume=

    On the power of algebraic branching programs of width two , author=. computational complexity , volume=. 2016 , publisher=

    work page 2016

  28. [28]

    The Power of Depth 2 Circuits over Algebras , booktitle =

    Chandan Saha and Ramprasad Saptharishi and Nitin Saxena , editor =. The Power of Depth 2 Circuits over Algebras , booktitle =. 2009 , url =. doi:10.4230/LIPICS.FSTTCS.2009.2333 , timestamp =

    work page doi:10.4230/lipics.fsttcs.2009.2333 2009

  29. [29]

    Stasys Jukna , title =. Oper. Res. Lett. , volume =. 2018 , url =. doi:10.1016/J.ORL.2018.02.003 , timestamp =

    work page doi:10.1016/j.orl.2018.02.003 2018

  30. [30]

    Electron

    Meena Mahajan and Prajakta Nimbhorkar and Anuj Tawari , title =. Electron. Colloquium Comput. Complex. , volume =. 2018 , url =. TR18-020 , timestamp =

    work page 2018

  31. [31]

    International symposium on mathematical foundations of computer science , pages=

    Fast parallel computation of polynomials using few processors , author=. International symposium on mathematical foundations of computer science , pages=. 1981 , organization=

    work page 1981

  32. [32]

    2025 , school=

    Diverse Solutions, Modifying Graph Eigenvalues and Bounded-Width ABPs , author=. 2025 , school=

    work page 2025