Computational Complexity in Analysis: A lecture held by Martin Ziegler in spring 2015 at TU Darmstadt
This lecture applies the classical (i.e. discrete) theory of computation
to problems usually pertaining to numerics, that is,
over continuous universes such as real numbers, vectors,
sequences, functions, subsets, and more generally
separable metric spaces.
As one particular highlight we learn the proof of
Harvey Friedman's
Ker-I Ko's
celebrated
connection
between smooth maximization/integration and P-vs-NP-vs-#P;
on the practical side we will actually implement
some of the reliable algorithms in unbounded precision
and compare their performance to the theoretical predictions.
Synopsis:
- Recap on discrete complexity:
- asymptotic cost
- time and space
- machine models
- L, P, NP1, NP, #P, PSPACE, EXP
- reductions and completeness
- parameterized complexity
- Real Complexity Theory:
- numbers, sequences, limits
- real functions and continuity
- maximizing polytime functions
- integration and solving ODEs
- solving Poisson's PDE
- analytic functions, enrichment
- practical implementation (iRRAM)
- Uniform Complexity of Operators
- TTE and computational complexity
- representing spaces of polynomial entropy
- adversary arguments and exponential entropy
- representing function spaces
- oracles and 2nd-order complexity
- (Basic Feasible Functionals)
- (2nd-order polytime W-reductions)
Homework/assignments/problems for the weekly tutorial classes:
01,
02,
03,
04,
05,
06,
07,
08,
09,
10,
11,
12.
Selected References:
- Ker-I Ko: Complexity
Theory of Real Functions, Birkhäuser (1991).
- Mark Braverman, Stephen Cook: Computing
over the Reals: Foundations for Scientific Computing,
Notices of the AMS (2006).
- Akitoshi Kawamura, Stephen Cook: Complexity
Theory for Operators in Analysis, ACM Transactions on Computation Theory 4 (2012).
- Akitoshi Kawamura, Hiroyuki Ota, Carsten Rösnick, Martin Ziegler:
Computational
Complexity of Smooth Differential Equations, Logical Methods in Computer Science (2014).
- Akitoshi Kawamura, Norbert Müller, Carsten Rösnick, Martin Ziegler:
Computational Benefit of Smoothness:
Parameterized Bit-Complexity of Numerical Operators on Analytic Functions and Gevrey's Hierarchy,
to appear in the Journal of Complexity.
- Akitoshi Kawamura, Florian Steinberg, Martin Ziegler:
On the Computational Complexity of the Dirichlet Problem for Poisson's Equation,
to appear in Mathematical
Structures in Computer Science
- Akitoshi Kawamura, Martin Ziegler:
Proc.
12th Int. Conf. on Computability and Complexity in Analysis (CCA 2015).
- Katrin Tent, Martin Ziegler (Freiburg!):
Computable
Functions of Reals