Pith. sign in

REVIEW 2 major objections 2 minor 13 references

P-NP separation in the BSS model over complexes implies separation of constant-free VP and VNP.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-25 21:21 UTC pith:MLMHQBJ6

load-bearing objection The paper proves that BSS P≠NP over C implies constant-free VP≠VNP (uniform and nonuniform), via reductions that the author claims preserve the no-constants restriction; the reverse stays a conjecture. the 2 major comments →

arxiv 2606.25121 v1 pith:MLMHQBJ6 submitted 2026-06-23 cs.CC

Intractability of Hilbert's Nullstellensatz implies algebraic hardness of permanent

Peter B\"urgisser This is my paper
classification cs.CC
keywords Blum-Shub-Smale modelValiant algebraic complexityHilbert NullstellensatzpermanentVP VNP separationconstant-free classesP-NP conjecture over C
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper proves a one-way implication between two prominent separation conjectures. If deciding feasibility of systems of polynomial equations over the complex numbers requires superpolynomial time in the Blum-Shub-Smale model, then the constant-free versions of Valiant's VP and VNP must also be separated, both in the uniform and nonuniform settings. A sympathetic reader cares because this transfers intractability from a geometric decision problem to the evaluation of the permanent, a central object in algebraic complexity. The argument relies on explicit reductions that stay within constant-free classes. The paper also states a conjecture for the opposite direction.

Core claim

We prove that P_C ≠ NP_C in the Blum-Shub-Smale model over C implies VP^0(u) ≠ VNP^0(u) of the uniform constant-free Valiant classes over C. The analogous statement holds for the nonuniform constant-free classes: P^0_C(nu) ≠ NP^0_C(nu) implies VP^0 ≠ VNP^0. In the reverse direction we conjecture that VNP_C notsubseteq closure of VP_C implies P_C(nu) ≠ NP_C(nu).

What carries the argument

Reductions from Hilbert's Nullstellensatz feasibility to permanent evaluation that preserve constant-free complexity classes without introducing constants.

Load-bearing premise

The constant-free restrictions of the BSS and Valiant models are defined so that the reductions between Nullstellensatz feasibility and permanent evaluation preserve the relevant complexity classes without introducing constants that would collapse the separation.

What would settle it

An explicit polynomial-time BSS algorithm over C for deciding feasibility of polynomial systems that does not induce a polynomial-time algorithm for permanent evaluation in the corresponding constant-free Valiant class.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • If P_C ≠ NP_C holds in the BSS model over C then the uniform constant-free classes satisfy VP^0(u) ≠ VNP^0(u).
  • If the nonuniform constant-free BSS classes are separated then the nonuniform constant-free Valiant classes are separated.
  • Intractability of Nullstellensatz feasibility directly yields algebraic hardness of the permanent in the constant-free setting.
  • Any collapse of the constant-free Valiant classes would force a corresponding collapse in the constant-free BSS classes.

Where Pith is reading between the lines

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

  • A proof that VP^0 equals VNP^0 would immediately yield a polynomial-time BSS algorithm for Nullstellensatz, giving an algebraic route to attacking the BSS conjecture.
  • The same style of reduction might transfer other decision problems between the geometric BSS setting and the algebraic permanent setting.
  • If the reverse conjecture is also true, the two separation statements become equivalent under the constant-free restriction.
  • Removing the constant-free restriction would likely allow constants to trivialize one side of the implication.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The manuscript proves one-way implications linking the P vs NP separation in the constant-free Blum-Shub-Smale model over C (both uniform and nonuniform) to the VP vs VNP separation in Valiant's constant-free algebraic complexity classes (uniform and nonuniform). Specifically, P_C ≠ NP_C implies VP^0(u) ≠ VNP^0(u), and P^0_C(nu) ≠ NP^0_C(nu) implies VP^0 ≠ VNP^0. The reverse direction is stated as a conjecture involving VNP_C notsubseteq closure of VP_C implying the BSS separation. The proofs rely on explicit reductions between Nullstellensatz feasibility and permanent evaluation that are claimed to preserve constant-freeness.

Significance. If the reductions are shown to stay strictly inside the constant-free classes, the result would formally transfer intractability from the BSS model to algebraic circuit complexity, providing a concrete bridge between two central open problems. The constant-free restriction is essential, as it prevents trivial collapses; the paper's explicit constructions (if they avoid introducing non-constant-free elements) constitute a technical contribution that could enable technique transfer between geometric and algebraic complexity.

major comments (2)
  1. [reduction from BSS to permanent (uniform case)] The load-bearing step is the claim that the reduction from a constant-free BSS machine deciding Nullstellensatz feasibility to a constant-free algebraic circuit computing permanent (or vice versa) introduces no field constants from C. This must be verified in the explicit construction; any implicit use of a specific complex number not generable by constant-free circuits would invalidate the transfer of the separation to the ^0 classes.
  2. [nonuniform reduction] In the nonuniform setting, the encoding of an arbitrary complex coefficient system into a permanent matrix must be shown to use only constants already present in the input instance without adding new ones from C. The abstract asserts this preservation, but the argument needs to address how coefficients that are themselves complex numbers are handled without violating the constant-free restriction.
minor comments (2)
  1. Notation for the uniform and nonuniform classes (VP^0(u), P^0_C(nu), etc.) should be defined once at the beginning and used consistently; occasional shifts between subscripts and superscripts reduce readability.
  2. The conjecture in the reverse direction is stated clearly but would benefit from a brief discussion of why the closure operation appears in the algebraic side but not the BSS side.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need to strengthen the verification of constant-freeness preservation in our reductions. We address the two major comments below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [reduction from BSS to permanent (uniform case)] The load-bearing step is the claim that the reduction from a constant-free BSS machine deciding Nullstellensatz feasibility to a constant-free algebraic circuit computing permanent (or vice versa) introduces no field constants from C. This must be verified in the explicit construction; any implicit use of a specific complex number not generable by constant-free circuits would invalidate the transfer of the separation to the ^0 classes.

    Authors: The uniform-case reduction (detailed in Section 3) simulates the constant-free BSS machine by translating its computation graph into an algebraic circuit whose gates use only the ring operations together with coefficients drawn exclusively from the input instance or from the set {0,1,-1}. Because the BSS machine itself is constant-free, no hardcoded complex scalars appear in the machine description, and the simulation therefore inherits the same restriction. We acknowledge that a line-by-line accounting of each gate would make this preservation more transparent and will add such a verification subsection in the revision. revision: yes

  2. Referee: [nonuniform reduction] In the nonuniform setting, the encoding of an arbitrary complex coefficient system into a permanent matrix must be shown to use only constants already present in the input instance without adding new ones from C. The abstract asserts this preservation, but the argument needs to address how coefficients that are themselves complex numbers are handled without violating the constant-free restriction.

    Authors: In the nonuniform setting the input to the constant-free BSS machine consists of the polynomial system whose coefficients are supplied as part of the instance; the reduction simply places those same coefficients into the entries of the permanent matrix. No additional constants from C are generated or required. We will expand the nonuniform reduction paragraph to state this mapping explicitly and to note that the constant-free restriction applies to the computational model rather than to the input data. revision: yes

Circularity Check

0 steps flagged

No circularity: one-way reductions between independently defined models

full rationale

The paper proves a logical implication from the BSS-model separation P_C ≠ NP_C to the constant-free Valiant separation VP^0(u) ≠ VNP^0(u) (and the nonuniform analogue) by exhibiting reductions from Nullstellensatz feasibility to permanent evaluation that are asserted to preserve the ^0 classes. No quoted equation, definition, or self-citation reduces the target separation back to a fitted quantity or to the input separation by construction; the models and classes are defined independently, and the result is a standard many-one reduction argument rather than a renaming, ansatz smuggling, or self-referential fit. The derivation is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof relies on the standard definitions of the BSS machine model over C, the ring of polynomials, and the constant-free restrictions of VP and VNP; these are background assumptions rather than new postulates.

axioms (2)
  • domain assumption The Blum-Shub-Smale model over C correctly captures polynomial-time computation with exact arithmetic on complex numbers.
    Invoked when comparing P_C and NP_C to the algebraic classes.
  • domain assumption Valiant's constant-free classes VP^0 and VNP^0 are defined without allowing nonzero constant inputs in the circuits.
    Central to the statement of the separations that are shown to follow from the BSS separation.

pith-pipeline@v0.9.1-grok · 5743 in / 1397 out tokens · 29193 ms · 2026-06-25T21:21:02.891936+00:00 · methodology

0 comments
read the original abstract

We study the logical relation of the P-NP separation conjecture in the Blum-Shub-Smale-model over the complex numbers with the P-NP separation conjecture in Valiant's algebraic model. This amounts to comparing Hilbert's Nullstellensatz Problem, that is, deciding feasibility of a given system of polynomial equations over the complex numbers, with the problem of evaluating the permanent of a given complex matrix. We compare the respective uniform models of computations and prove that $P_C\ne NP_C$ in the Blum-Shub-Smale-model over $C$ implies the separation $VP^0(u)\ne VNP^0(u)$ of the uniform versions of Valiant's constant-free complexity classes over $C$. For the nonuniform models we show the analogous implication: the separation $P^0_C(nu)\ne NP^0_C(nu)$ of the nonuniform, constant-free Blum-Shub-Smale classes over $C$ implies the separation $VP^0\ne VNP^0$ of Valiant's constant-free complexity classes over $C$. In the reverse direction, we conjecture that $VNP_C\not\subseteq\overline{VP}_C$ implies that $P_C(nu)\ne NP_C(nu)$.

discussion (0)

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

Reference graph

Works this paper leans on

13 extracted references · 2 canonical work pages

  1. [1]

    On the complexity of numerical analysis.SIAM J

    [ABKPM09] Eric Allender, Peter B¨ urgisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen. On the complexity of numerical analysis.SIAM J. Comput., 38(5):1987–2006, 2008/09. [AF22] Robert Andrews and Michael A. Forbes. Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals. InSTOC ’22—Proceedings of the 54th Ann...

    work page arXiv 1987

  2. [2]

    Algebraic settings for the problem “P̸= NP?”

    [BCSS96] Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale. Algebraic settings for the problem “P̸= NP?”. InThe mathematics of numerical analysis (Park City, UT, 1995), volume 32 ofLectures in Appl. Math., pages 125–144. Amer. Math. Soc., Providence, RI,

    1995

  3. [3]

    [B¨ ur01] Peter B¨ urgisser

    Selected papers in honor of Manuel Blum (Hong Kong, 1998). [B¨ ur01] Peter B¨ urgisser. On implications between P-NP-hypotheses: decision versus computation in algebraic com- plexity. InMathematical foundations of computer science, 2001 (Mari´ ansk´ e L´ azn˘ e), volume 2136 ofLecture Notes in Comput. Sci., pages 3–17. Springer, Berlin,

    1998

  4. [4]

    [Can88a] John Canny.The complexity of robot motion planning, volume 1987 ofACM Doctoral Dissertation Awards

    arXiv:2406.06217 To appear. [Can88a] John Canny.The complexity of robot motion planning, volume 1987 ofACM Doctoral Dissertation Awards. MIT Press, Cambridge, MA,

    work page arXiv 1987

  5. [5]

    Generalized characteristic polynomials

    [Can89] John Canny. Generalized characteristic polynomials. InSymbolic and algebraic computation (Rome, 1988), volume 358 ofLecture Notes in Comput. Sci., pages 293–299. Springer, Berlin,

    1988

  6. [6]

    Demystifying the border of depth-3 algebraic circuits

    [DDS22] Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena. Demystifying the border of depth-3 algebraic circuits. In2021 IEEE 62nd Annual Symposium on Foundations of Computer Science—FOCS 2021, pages 92–103. IEEE Computer Soc., Los Alamitos, CA,

    2021

  7. [7]

    Separated borders: exponential-gap fanin-hierarchy theorem for approx- imative depth-3 circuits

    [DS22] Pranjal Dutta and Nitin Saxena. Separated borders: exponential-gap fanin-hierarchy theorem for approx- imative depth-3 circuits. In2022 IEEE 63rd Annual Symposium on Foundations of Computer Science— FOCS 2022, pages 200–211. IEEE Computer Soc., Los Alamitos, CA,

    2022

  8. [8]

    Quantifier elimination in the theory of an algebraically-closed field

    [Ier89] Douglas Ierardi. Quantifier elimination in the theory of an algebraically-closed field. InProc. 21st Annual ACM Symposium on Theory of Computing (STOC 1989), pages 138–147,

    1989

  9. [9]

    [Koi97a] Pascal Koiran

    Special issue for the Foundations of Computational Mathematics Conference (Rio de Janeiro, 1997). [Koi97a] Pascal Koiran. Elimination of constants from machines over algebraically closed fields.J. Complexity, 13(1):65–82,

    1997

  10. [10]

    Randomized and deterministic algorithms for the dimension of algebraic varieties

    [Koi97b] Pascal Koiran. Randomized and deterministic algorithms for the dimension of algebraic varieties. In38th Annual Symposium on Foundations of Computer Science, FOCS 1997, Miami Beach, Florida, USA, Oc- tober 19-22, 1997, pages 36–45. IEEE Computer Society,

    1997

  11. [11]

    Circuits versus trees in algebraic complexity

    [Koi00] Pascal Koiran. Circuits versus trees in algebraic complexity. InSTACS 2000 (Lille), volume 1770 ofLecture Notes in Comput. Sci., pages 35–52. Springer, Berlin,

    2000

  12. [12]

    Valiant’s model: from exponential sums to exponential products

    INTRACTABILITY OF HILBERT’S NULLSTELLENSATZ IMPLIES HARDNESS OF PERMANENT 25 [KP06] Pascal Koiran and Sylvain Perifel. Valiant’s model: from exponential sums to exponential products. In Mathematical foundations of computer science 2006, volume 4162 ofLecture Notes in Comput. Sci., pages 596–607. Springer, Berlin,

    2006

  13. [13]

    [Val79] Leslie G. Valiant. Completeness classes in algebra. InConference Record of the Eleventh Annual ACM Symposium on Theory of Computing (Atlanta, Ga., 1979), pages 249–261. ACM, New York,

    1979