Polynomiales Laufzeitverhalten (Komplexitätstheorie / Theoretische Informatik)

Welche Probleme betrachtet man in der Theorie noch als "machbar" und welche sind "widerspenstig"? Was ist mit den ominösen Klassen P und NP gemeint? Und was besagt die erweiterte Church-Turing-These?
* Das GANZ NEUE Buch: weitz.de/GDM/
* Das NEUE Buch: weitz.de/PP/
* Skript: weitz.de/files/ti-skript.pdf
* Ausführliche Playlist zur Komplexitätstheorie (Sommersemester 2014): • Theoretische Informati...
* Das Video im Playlist-Kontext: weitz.de/y/msdFAG0fv5s?list=PL...
* Liste aller Videos: weitz.de/haw-videos/
* Das etwas andere Mathe-Lehrbuch: weitz.de/KMFI/
* "FAQ": weitz.de/youtube.html
00:00 Einleitung
04:22 polynomiale Laufzeit
13:16 Entscheidungsprobleme
17:46 P und NP: Zeitmessung für Turingmaschinen
29:08 P ist robust bzgl. Varianten von Turingmaschinen
37:46 P ist robust bzgl. verschiedener Rechnermodelle