A Theory of Complexity, Condition and Roundoff
summary
Defines a finite-precision BSS machine that rounds every intermediate real to x(1+δ) with |δ| ≤ u and fixes precision k = log2(1/u). Proposes input size = length + log(condition) and an accuracy cost = minimal k that guarantees correctness. Introduces classes P_ro (polynomial arithmetic and precision bounds), P_dir (time independent of precision), NP_ro with witness y whose condition stays polynomially related, and an algebraic-circuit sign decision problem proved NP_ro-complete; determinant computation takes O(n^3) arithmetic independent of precision.
AI-written summary · about