A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF. (1st February 2015)

• Record Type: Journal Article
• Authors: CUCKER, FELIPE
• Is Part Of: Forum of mathematics. Volume 3(2015)
• Publication Date: 2015-02-01
• Subjects: 68Q15 (primary), -- 68Q17 (secondary); Mathematics -- Periodicals; 510
• DOI: 10.1017/fms.2015.2
• Languages: English
• ISSNs: 2050-5094

Abstract

Abstract : We develop a theory of complexity for numerical computations that takes into account the condition of the input data and allows for roundoff in the computations. We follow the lines of the theory developed by Blum, Shub and Smale for computations over $\mathbb{R}$ (which in turn followed those of the classical, discrete, complexity theory as laid down by Cook, Karp, and Levin, among others). In particular, we focus on complexity classes of decision problems and, paramount among them, on appropriate versions of the classes $\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{EXP}$ of polynomial, nondeterministic polynomial, and exponential time, respectively. We prove some basic relationships between these complexity classes, and provide natural NP-complete problems.