Conjecture 3.13 — Blum, Cucker, Shub and Smale

Definitions and mathematical statement

Consider a family of polynomial inputs $P_1,\ldots,P_m$ in a common, variable number of variables $x_1,\ldots,x_n$, represented by a total of $N$ coefficients. The promise is that the polynomials have no common zero in $\mathbb C^n$. The task is to output coefficients of polynomials $A_1,\ldots,A_m$ satisfying the polynomial identity \[ \sum_{i=1}^m A_iP_i=1. \] The coefficient field, input monomial representation, and output representation are not specified. Interpreting the polynomials in $\mathbb C[x_1,\ldots,x_n]$ gives one natural algebraic setting, but the exact computational field must be fixed with the model.

The conjecture excludes a polynomial-step algorithm: for every fixed absolute exponent $c>0$, no single program solves this search problem on every promised input in at most $N^c$ steps. The exponent is independent of the number of variables, number of polynomials, degrees, and input coefficients. The source's attribution places the question in the Blum--Cucker--Shub--Smale complexity context, but the allowed arithmetic/test operations and constants are not supplied.

An exact formulation must distinguish arithmetic-operation complexity from bit complexity, dense from sparse coefficient encodings, and explicit coefficient output from straight-line/circuit output. The conjectured absence of every polynomial-step bound is not by itself a specified exponential lower bound, despite the research summary's wording. It is a search-complexity question, not an automatically established NP-hardness assertion.

Short English statement

Given polynomials with no common complex zero, prove that no polynomial-step program always outputs explicit Bézout identity coefficients. Fix the coefficient encoding, output representation, and computational model before stating the lower bound.

Sources

• Michel Waldschmidt, Open Diophantine Problems (2004), Conjecture 3.13, https://arxiv.org/abs/math/0312440; accessed 2026-07-29, source-TeX extraction. The item is attributed to Blum, Cucker, Shub, and Smale.
• Local registry data/unsolvedmath/problems.json, permanent UnsolvedMath ID $8700031$, source code catalogue entry, Conjecture 3.13 --- Blum, Cucker, Shub and Smale. Dataset attribution: Ulam AI and the UnsolvedMath Contributors.
• The research summary connects the question to BCSS complexity and the effective Nullstellensatz but supplies no separate primary publication or model specification.