Complexity and real computation: A manifesto

Abstract

Finding a natural meeting ground between the highly developed complexity theory of computer science - with its historical roots in logic and the discrete mathematics of the integers - and the traditional domain of real computation, the more eclectic less foundational field of numerical analysis - with its rich history and longstanding traditions in the continuous mathematics of analysis - presents a compelling challenge. Here we illustrate the issues and pose our perspective toward resolution.