Paper Info
Title
Invitation to Real Complexity Theory: Algorithmic Foundations to Reliable Numerics with Bit-Costs.
Abstract
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.
Year
Venue
Field
2018
arXiv: Computational Complexity
Discrete mathematics,Continuous function,Correctness,Theoretical computer science,Mathematical proof,PSPACE,Euclidean geometry,Real number,Mathematics,Approximation error,Software development
DocType
Volume
Citations 
Journal
abs/1801.07108
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Akitoshi Kawamura110215.84
Martin Ziegler273.33