Contemporary Mathematics Volume 604, 2013 Topics in real and complex number complexity theory Martijn Baartse and Klaus Meer Abstract. The paper intends to introduce into topics relevant in real and complex number complexity theory. This is done in a survey style. Taking as starting point the computational model introduced by Blum, Shub, and Smale the following issues are addressed: Basic results concerning decidability and NP-completeness, transfer results of open questions between different models of computation, structural complexity inside NPR, computational universality, and probabilistically checkable proofs over the real and complex numbers. 1. Introduction Complexity theory as a mathematical discipline is a relatively young subject. In a systematic way it was basically developed since the 1970’s in Theoretical Com- puter Science based on the Turing machine as underlying model of computation. This led to a theory nowadays basically devoted to study complexity issues of dis- crete problems over finite structures. Problem instances are coded by sequences of bits and the complexity of algorithms is measured by counting the number of elementary bit operations necessary. It seems that Turing himself was as well inter- ested in complexity and accuracy issues of numerical algorithms. He also addressed an idealized model in which floating-point numbers are used as kind of entities and was working on notions like the conditioning of a problem [104]. In contrast to the observation that complexity theory often is considered as a discipline in computer science mathematicians have designed and analysed algo- rithms already since centuries. Some of the most important and prominent ones were developed long before computers existed. Their inventors certainly had as well an intuition about complexity issues, though often under other perspectives. Think about algorithms like Gaussian elimination, Newton’s method and notions like the order of convergence in numerical analysis, or algorithms for deciding the existence of complex solutions of a polynomial system related to Hilbert’s Nullstellensatz. Algorithms located in more classical areas of mathematics usually work with objects from uncountable continuous domains like the real or complex numbers, respectively. Often the number of basic arithmetic operations and test operations 2010 Mathematics Subject Classification. Primary 68Q05, 68Q15 Secondary 68Q17, 03D15, 03D35. The authors gratefully acknowledge support of both authors by project ME 1424/7-1 of the Deutsche Forschungsgemeinschaft DFG. The second author wants to cordially thank L.M. Pardo and J. L. Monta˜ na for the hospitality during the Santal´ o summer school in Santander, on which occasion this paper was written. c 2013 American Mathematical Society 1
Previous Page Next Page