Separation of P_R from NP_R in the Blum–Shub–Smale Model

Separation of P_R from NP_R in the Blum–Shub–Smale Model

Definitions and mathematical statement

An ordered-real Blum--Shub--Smale machine stores exact real numbers and performs field operations and equality/order tests at unit cost, using finitely many built-in real constants. Input length is the number of real coordinates, not their binary precision. Let $\mathrm P_{{\mathbb{R}}}$ consist of sets decided in polynomially many deterministic steps. A set belongs to $\mathrm{NP}_{{\mathbb{R}}}$ if membership is equivalent to existence of a polynomial-length real witness accepted by such a verifier. The assertion is \[ \mathrm P_{{\mathbb{R}}}\ne\mathrm{NP}_{{\mathbb{R}}}. \] The real constants belong to the fixed machine; it does not receive arbitrary input-dependent advice. This is a real-computation separation, not merely the classical binary $\mathrm P$ versus $\mathrm{NP}$ question.

Formulation and concept references: [S1].

Short English statement

In exact real-number computation, are some problems with short real certificates impossible to solve in polynomially many deterministic operations?

Research attempt

Current frontier.

The ordered-real model and its polynomial feasibility problems are described in [S1]; its comparisons with binary computation do not identify the two models. In particular, a large binary encoding of a register is not a lower bound on the number of BSS steps. The source explains the complete-problem and geometric viewpoints, but does not establish the separation requested here. No theorem verified in this research establishes that separation with the finite arbitrary-real-constant convention intact.

Attack route.

One route seeks lower bounds from the topology of semialgebraic decision sets. Another tries to transfer binary hardness, but must account for exact arithmetic and built-in real constants. A third would diagonalize against real machines; a countable enumeration of rational-constant programs does not cover the present machines. We pursue a concrete topological counting argument and challenge it with a family whose topology is exponentially complicated but whose computation is short. This tests the quantitative strength of the chosen invariant before using it on a complete problem.

Attempt: degree growth along a computation.

Fix a machine, an input dimension, and a line in the input space, with its coordinates affine functions of a real parameter $x$. Its built-in real constants are treated as coefficients, not as advice chosen separately for each input. On any fixed computation path of at most $T$ operations, every register is a rational function of $x$ whose numerator and denominator have degree at most $2^T$.

To prove the bound, start with affine polynomials and constant denominators. If the degrees at one stage are at most $D$, addition or subtraction of two fractions gives numerator $ad\pm bc$ and denominator $bd$, of degrees at most $2D$. Multiplication and division have the same bound, when the latter is defined. Cancellation can only lower the degrees. Induction proves the claim. No bound on coefficient sizes, and no algebraicity of the real constants, was assumed.

An order or equality test of a rational expression can change its outcome only at a zero of its numerator or denominator. An identically zero polynomial gives a fixed test outcome and contributes no roots. Along one path there are at most $T$ tests and division-domain conditions, so their exceptional points number at most $C T2^T$. There are at most $3^T$ test paths, since a sign test has at most three outcomes. After collecting all such roots, every remaining open interval follows a fixed path and has a fixed acceptance outcome. Including the isolated exceptional points gives \begin{equation}\label{wsref-0-65-71-31-37-32-2d-63-6f-6d-70-6f-6e-65-6e-74-73} \#\{\text{connected components on the input line}\} \le C'(T+1)6^T. \end{equation} The constants absorb harmless conventions about arithmetic nodes and halt states. At exceptional points the machine is still required to decide correctly, but they can add only their number of singleton components.

Thus a line section with $K$ connected components yields only $T\ge c\log K-O(\log\log K)$ by this argument. Exponentially many components in a dimension parameter supply a linear or polynomial bound, not automatically a superpolynomial one. This does not rule out every possible topological lower-bound method; it identifies the limitation of this particular one-dimensional counting statistic.

Attempt: an exact fast family with exponential topology.

Define \[ P_0(x)=x,\qquad P_{j+1}(x)=2P_j(x)^2-1. \] The cosine identity $2\cos^2\theta-1=\cos(2\theta)$ proves by induction \begin{equation}\label{wsref-0-65-71-31-37-32-2d-63-68-65-62-79-73-68-65-76} P_j(\cos\theta)=\cos(2^j\theta). \end{equation} For $j\ge1$, the set $\{x\in[-1,1]:P_j(x)>0\}$ has exactly $2^{j-1}+1$ connected components. Indeed $\theta\mapsto\cos\theta$ is a bijection from $[0,\pi]$ to $[-1,1]$, and the $2^j$ simple zeros of $\cos(2^j\theta)$ alternate its sign, with positive intervals at both endpoints. Nevertheless evaluation uses only $j$ squarings, $j$ multiplications by $2$, $j$ subtractions, and one sign test.

To make this a legitimate variable-size BSS decision family, let an input have $j+1$ real coordinates, use the first as $x$, and use the remaining coordinates only to specify length. A fixed uniform machine loops $j$ times and decides membership in polynomial, in fact linear, time. Padding does not give input-dependent constants. Hence exponentially many components and degree $2^j$ can coexist with membership in $\mathrm P_{{\mathbb{R}}}$. This exact example falsifies the proposed inference from exponential algebraic complexity to superpolynomial running time.

It also has a short real-witness presentation: introduce $y_0,\ldots,y_j$ and impose \[ y_0=x,\qquad y_{i+1}=2y_i^2-1,\qquad y_j>0. \] These are quadratic equations and one inequality. They illustrate why introducing witnesses for arithmetic gates does not in itself create a hard instance: here the witnesses are uniquely determined and quickly computed. Real feasibility as a complete problem, discussed in [S1], requires hardness for arbitrary systems, not every special system produced by a short straight-line recurrence.

Attempt: where a stronger strategy would have to change.

One might try to prove that every accepting computation for a carefully chosen feasibility instance requires high-degree tests. The degree bound above would then turn a degree lower bound $D$ into only $T\ge\log_2D$. A superpolynomial time conclusion from that route would require a correspondingly enormous degree lower bound, or a complexity measure which cannot be cheaply generated by repeated squaring. The Chebyshev family shows why merely counting real roots of a high-degree polynomial is not that measure.

The binary-hardness route has a different obstruction. On binary inputs, a real machine can generate integers with exponentially many binary digits in polynomially many squarings. A faithful Turing simulation must pay for such arithmetic; assuming its cost is polynomial would silently change models. Conversely, a single fixed real constant cannot simply be used as a unit-cost table lookup of arbitrary bits: a valid BSS algorithm still must extract any purported information with its allowed field operations and tests. Neither side of that informal argument yields a separation.

Finally, enumerating only machines whose constants are rational or algebraic would prove, at most, a different statement. The path-degree calculation is robust under arbitrary real coefficients, but a diagonal construction would need a similarly robust treatment of all choices of finitely many real constants. No such diagonal language with the required $\mathrm{NP}_{{\mathbb{R}}}$ verification has been constructed here.

Stress test.

The component bound counts the whole decision tree, not just the path of one sample input. Denominator roots are retained, so division has not been treated as a globally defined polynomial operation. The bound is on a line section, not on arbitrary high-dimensional Betti numbers. A negative result for restricted algebraic computation trees would also require justification before being transferred to the full machine model.

The polynomial family above uses only the constants $1$ and $2$, and its component count follows from an exact trigonometric identity. Numerical plots or counting approximate zeros are unnecessary. It is not a counterexample to $\mathrm P_{{\mathbb{R}}}\ne\mathrm{NP}_{{\mathbb{R}}}$: it is an easy language deliberately chosen to refute a candidate lower-bound lemma. No implication to binary $\mathrm P\ne\mathrm{NP}$ or its converse has been presumed.

Outcome.

Outcome: Exploratory approach with unresolved gap.

The attempt proves a path-degree bound and a corresponding component-count bound valid with arbitrary fixed real constants. It then gives an explicit family showing that exponential degree and topology are insufficient for the proposed separation argument. These elementary deductions identify a failed route, not a new lower bound for a complete real-feasibility problem. A successful continuation needs a stronger invariant or a different uniform hardness argument that survives exact arithmetic and the full constant convention.

Sources

• S1 Computing over the Reals: Where Turing Meets Newton, author exposition associated with2004 publication. https://www.cs.cmu.edu/~lblum/PAPERS/TuringMeetsNewton.pdf. Catalogue formulation source.