Invitation to Real Complexity Theory: Algorithmic Foundations to Reliable Numerics with Bit-Costs
For researchers in numerical computation and theoretical computer science, it proposes a foundational framework to bring rigorous algorithmic analysis to continuous problems, though it remains a programmatic advertisement without concrete results.
The paper advocates for Real Complexity Theory, a resource-oriented foundation for rigorous computations over continuous domains using bit-costs, aiming to replace empirical validation in numerical engineering with provable correctness and efficiency. It claims to offer sound semantics, closure under composition, realistic runtime predictions, and optimality proofs by relating to complexity classes like NP, #P, and PSPACE.
While concepts and tools from Theoretical Computer Science are regularly applied to, and significantly support, software development for discrete problems, Numerical Engineering largely employs recipes and methods whose correctness and efficiency is demonstrated empirically. We advertise REAL COMPLEXITY THEORY: a resource-oriented foundation to rigorous computations over continuous universes such as real numbers, vectors, sequences, continuous functions, and Euclidean subsets: in the bit-model by approximation up to given absolute error. It offers sound semantics (e.g. of comparisons/tests), closure under composition, realistic runtime predictions, and proofs of algorithmic optimality by relating to known classes like NP, #P, PSPACE.