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

In the standard ordered-real Blum–Shub–Smale model, machines use finitely many built-in real constants, real-valued registers, exact field operations (+,-,multiplication,division where defined) and order/equality tests at unit cost. Inputs are finite real vectors and size is vector length. Let P_R be decision problems solved by deterministic machines in polynomially many steps, and NP_R those with polynomial-length real witnesses verifiable in P_R. The assertion is P_R != NP_R.

Source: Computing over the Reals: Where Turing Meets Newton, author exposition associated with2004 publication.

Status Open Status review date not recorded in this edition

Listed by ProofAtlas. Status qualification is attributed to ProofAtlas; no full resolution is certified here.