We develop a complexity theory for approximate real computations. We first produce a theory for exact computations but with condition numbers. The input size depends on a condition number, which is not assumed known by the machine. The theory admits deterministic and nondeterministic polynomial time recognizable problems. We prove that P is not NP in this theory if and only if P is not NP in the BSS theory over the reals. Then we develop a theory with weak and strong approximate computations. This theory is intended to model actual numerical computations that are usually performed in floating point arithmetic. It admits classes P and NP and also an NP-complete problem. We relate the P vs. NP question in this new theory to the classical P vs. NP problem.

This paper deals with complexity classes ${\cal P}_{\Bbb C}$ and ${\cal NP}_{\Bbb C}$ as they were introduced over the complex numbers by Blum, Shub, and Smale [Bull. Amer. Math. Soc., 21 (1989), p. 1]. Under the assumption ${\cal P}_{\Bbb C} \ne {\cal NP}_{\Bbb C}$ the existence of noncomplete problems in ${\cal NP}_{\Bbb C}$ not belonging to ${\cal P}_{\Bbb C}$ is established.