SoSe 2011 » Reelle Komplexität
Ziegler

Übersicht

Beiträge

Aktuelles

03.03.2011

Vorbesprechung am 11.4.2011 um 14h25 im S2|02-A313. Der erste Vortrag findet statt am 2.5.2011 um 14h25 im S2|02-A313

 

Veranstalter

Name	Raum	Tel.
Ziegler, Martin

 

Vorlesung

Tag	Uhrzeit	in Raum
Montags	14:25 - 16:05	S2|02-A313

 

Literatur

• L. Blum, F. Cucker, M. Shub and S. Smale, Complexity and Real Computation, Springer (1998) (HeBIS, Wellnitz, Buch Habel, Amazon)
• L. Blum, M. Shub, S. Smale, “On a Theory of Computation Over the Real Numbers; NP Completeness, Recursive Functions and Universal Machines,” FOCS; 88; Bulletin of the AMS, Vol. 21:1 pp.1-46 (1989, projecteuclid.org/euclid.bams/1183555121
• Ker-I Ko: "Complexity Theory of Real Functions", Springer (1991) (HeBIS, Wellnitz, Buch Habel, Amazon)
• Klaus Weihrauch: "Computable analysis", Springer (2000) (HeBIS, Wellnitz, Buch Habel, Amazon)
• Ker-I Ko, Harvey Friedman: Computational Complexity of Real Functions. Theor. Comput. Sci. 20: 323-352 (1982) (HeBIS)
• Brattka, Hertling, Weihrauch: "A Tutorial on Computable Analysis", http://www.springerlink.com/content/q8m3614067427312/

 

Kooperation

gemeinsam mit PD Dr. Ulrike Brandt vom Fachbereich Informatik

 

Einleitung

Sicher haben Sie schon vom Milleniumsproblem "P versus NP" gehört; vielleicht auch vom verwandten "NP versus PSPACE". Hierbei geht es um die Beziehungen zwischen Komplexitätsklassen diskreter Rechenaufgaben, d.h. über natürlichen Zahlen bzw. endlichen Binärfolgen.

Für das Rechnen mit reellen Zahlen gibt es zwei diametrale Algorithmen-Konzepte:

1. als Programm über den arithmetischen Operationen und Vergleichen: wohlgemerkt exakt
2. durch Approximation mit Brüchen (d.h. Zähler und Nenner natürliche Zahlen) bis auf vorgebbaren Absolutfehler

Hier tauchen die Konzepte P und NP  in überraschender Weise wieder auf und erklären, warum manche numerischen Aufgaben so viel Rechenaufwand aufwerfen.

 

Themenliste und Termine

1. Grundlagen struktureller diskreter Komplexitätstheorie I (deterministische und nichtdeterministische Turingmaschinen, Asymptotik, polynomielle Laufzeit und Speicherplatz) : Schwagenscheidt, 2.5.
2. Grundlagen struktureller diskreter Komplexitätstheorie II (Reduktion, NP- und PSPACE-vollständige Probleme) : Bitterlich, 9.5.

3. Berechenbarkeit und Komplexität reeller Zahlen (mehrere äquivalente Definitionen, Eigenschaften, Gegen-/Beispiele) : Wietschel 16.5.
4. Berechenbarkeit reeller Funktionen auf [0,1] (Definition, Hauptsatz, effektiver Weierstraß, Beispiele) : Franz 23.5.
5. Komplexität reeller Zahlen und Funktionen (sinnlose und sinnvolle Definition, Beispiele) : Neeb 30.5.
6. Komplexität des Maximums einer polynomialzeitberechenbaren Funktion : Thies 6.6.
7. Komplexität des Integrals einer polynomialzeitberechenbaren Funktion

8. BSS-Rechenmodell: Motivation, Definition, Beispielalgorithmen : Chebotar 20.6.
9. Pfadzerlegung, unberechenbare reelle Funktionen : Sokoli 27.6. im S2|15-201
10. Komplexitätsklasse NP über Ringen {0,1}, ℕ, ℝ, ℂ: Deiseroth 4.7.
11. P-versus-NP über ℝ und ℂ, Entscheidbarkeit von NP: Schwagenscheidt 11.7.
12. Komplexität und Quantenlogik: Ziegler 18.7.

     

    Impressum | Datenschutzerklärung