Complexity Theory of Real Functions

Mathematics background.- Notation.- 1 Basics in Discrete Complexity Theory.- 1.1 Models of computation and complexity classes.- 1.2 NP-completeness.- 1.3 Polynomial-time hierarchy.- 1.4 Relativization.- 1.5 Probabilistic complexity classes.- 1.6 Complexity of counting.- 1.7 One-way functions.- 1.8 Polynomial-size circuits and sparse sets.- 2 Computational Complexity of Real Functions.- 2.1 Computable real numbers.- 2.2 Complexity of computable real numbers.- 2.3 Computable real functions.- 2.4 Complexity of computable real functions.- 2.5 Computable multi-dimensional functions.- 2.6 Partial computable real functions and recursively open sets.- 2.7 Computable numerical operators.- 3 Maximization.- 3.1 Computability of the maximum points.- 3.2 Maximization and nondeterminism.- 3.3 Maximum values and NP real numbers.- 3.4 Complexity of NP real numbers.- 3.5 Maximization and NP real functions.- 3.6 Hierarchy of min-max operations.- 3.7 Complexity of NP real functions.- 3.8 Open questions.- 4 Roots and Inverse Functions.- 4.1 Computability of roots.- 4.2 Complexity of roots and inverse modulus of continuity.- 4.3 Complexity of roots and differentiability.- 4.4 Log-space computable real functions.- 4.5 Log-space computability of roots of one-to-one functions.- 4.5.1 A discrete version.- 4.5.2 Log-space computability of roots.- 4.5.3 Differentiability does not help131 One-way functions and roots of two-dimensional one-to-one functions.- 4.6.1 A sufficient condition.- 4.6.2 Strong one-way functions.- 4.6.3 Necessary conditions137 Roots of one-dimensional k-to-one functions.- 4.7.1 Inverse modulus of continuity.- 4.7.2 Roots of three-to-one functions.- 4.7.3 Roots of four-to-one functions.- 4.8 Open questions.- 5 Measure and Integration.- 5.1 Recursive measure theory.- 5.1.1 Recursively approximable sets.- 5.1.2 Recursively approximable functions.- 5.1.3 Recursive approximability versus computability.- 5.2 Polynomial-time approximation.- 5.3 Polynomial-time approximation and probabilistic computation.- 5.4 Complexity of integration.- 5.5 Open questions.- 6 Differentiation.- 6.1 Computability of derivatives.- 6.2 Derivatives of analytic functions.- 6.3 Functions of bounded variations.- 7 Ordinary Differential Equations.- 7.1 ODEs without the Lipschitz condition.- 7.2 ODEs with the Lipschitz condition: upper bound.- 7.2.1 Polynomial-space computable real numbers and real functions.- 7.2.2 Proof for upper bound.- 7.3 ODEs with the Lipschitz condition: lower bound.- 7.3.1 A discrete initial value problem.- 7.3.2 The basic construction.- 7.3.3 Proofs for lower bounds.- 7.4 Open questions.- 8 Approximation by Polynomials.- 8.1 Polynomial Version of the Weierstrass approximation theorem.- 8.2 Best Chebyshev approximation: complexity of the errors.- 8.3 Best Chebyshev approximation: complexity of the approximation functions.- 9 An Optimization Problem in Control Theory.- 9.1 A discrete version.- 9.2 The basic construction.- 9.3 The complexity of LCTEAM.