MACIS 2015 Session (SS11): Real Complexity Theory and Practice

Turing machine computing π (picture 'Maquina' modified from wikimedia>

MACIS 2015:  
<a href=Home, Sessions Page


Aim and Scope

Rigorous numerical methods are increasingly applied in order to solve 'purely' analytical problems such as Note that the above Computer-Assisted Proofs, as well as solutions to other recent challenges in real computation with prescribed output error, are generally ad-hoc and hand-tailored to each specific instance: in terms of computational approach, underlying libraries/software, and notion of efficiency.

Real Complexity Theory — a synthesis of Computable Analysis and (discrete) Complexity Theory — on the other hand does provide for a sound algorithmic foundation to computation by approximation over continuous universes such as real numbers, vectors, sequences, functions, subsets, and operators. The field was initiated by Harvey Friedman and Ker-I Ko (1982), connecting maximization and integration of (smooth) 1D functions to the discrete complexity classes NP and #P, respectively. Among the many subsequent works we mention [Müller'87], [Ko'91], [Kapron&Cook'96], [Labhalla&Lombardi&Moutai'01], [Weihrauch'03], [Schröder'04], [Du&Yap'05], [Braverman&Cook'06], [Rettinger'07], [Skordev'08], [Hotz'09], [Tent&Ziegler'10], [Bournez&Graca&Pouly'11], [Kawamura&Cook'12], [Feree&Gomaa&Hoyrup'13], [Kawamura&Ota&Rösnick&Ziegler'14], [Müller&Ziegler'14], [Rösnick'15], [Kawamura&Müller&Rösnick&Ziegler'15]

The present Special Session aims to connect both theory and actual computations. Parameterized analyses promise fine-grained predictions on the runtime and memory consumption of actual implementations; while reductions and adversary arguments can assert the optimality of an algorithm under consideration.

complexity-theoretic hierarchy

Topics (including, but not limited to)

function computable in exponential but not in polynomial time infinitely-often differentiable 'pulse' function polynomial-time computable smooth function whose maximum is not polynomial-time computable unless P=NP


Fragments of code for iRRAM
REAL jmmuller(int m){ 
REAL x = (REAL)(11)/(REAL)(2),
   t, y = (REAL)(61)/(REAL)(11); 
while (m>1) { 
   x=y; y=t; m--; }  return(y); } 
Example due to Jean-Michel Muller:
Don't try this at home (i.e. with double :-)

REAL *Eigenvector2D_wrong(
   REAL A11, REAL A12, REAL A22);

REAL *Eigenvector2D(BOOL degenerate,
   REAL A11, REAL A12, REAL A22);
Incorrect declaration of C++ function computing an eigenvector to a given symmetric 2x2 matrix, corrected using enrichment

// a<b, f(a)<0, f(b)>0
while (!bound(b-a,p)) {
   REAL y=f((a+b)/3), z=f(2*(a+b)/3);
   if (choose(z>0,y<0)==1)
   b=2*(a+b)/3;  else a=(a+b)/3; }
Trisection using a multivalued (aka soft) test


Submission Guidelines