Complexity Theory for FMB
("Module 1")

Course texts

1. Viggo Stoltenberg-Hansen. Computability and complexity on discrete structures. Lecture notes, March 2007.
2. Peter Hertling. Is the Mandelbrot set computable? Mathematical Logic Quarterly 2005 (51), 5 - 18.
3. Vasco Brattka. The emperor's new recursiveness: the epigraph of the exponential function in two models of computability. In: Masami Ito and Teruo Imaoka, editors, Words, Languages & Combinatorics III, pp 63 - 72. World Scientific Press 2003.

Some links

• Gödel's lost letter and P = NP. (Blog about complexity theory).
• Complexity Theory 10 hp.
• Complexity Zoo
• Knowledge, Creativity and P versus NP by Avi Wigderson 2009.
• List of NP-complete problems at Wikipedia.