Speaker:
Martin Ziegler
Title:
Algebraic Complexity Theory and Quantum Logic
Abstract:
Algebraic models of computation (like register machines)
make one operation per step regardless of the value processed.
They underly algorithms for sorting or in computational geometry.
As opposed to bit models, algebraic methods permit to
establish non-trivial lower bounds:
We recall Morgenstern's elegant proof that the fast
fourier transform is optimal; then proceed to the structural
complexity theory and prove the quantum satisfiability problem
complete for NP_R^0: a well-known discrete complexity class
between NP and PSPACE. (Joint work with Christian Herrmann.)