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.
REAL jmmuller(int m){ REAL x = (REAL)(11)/(REAL)(2), t, y = (REAL)(61)/(REAL)(11); while (m>1) { t=111-(1130-3000/x)/y; 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; } return((a+b)/2);Trisection using a multivalued (aka soft) test |