Seite 1 von 1

Letzte Vorlesung, Fehler und Folien

BeitragVerfasst: 05 Feb 2014, 18:58
von gert.smolka
Nach der Vorlesung wurde ich auf 2 Fehler in meinem Tafelanschrieb aufmerksam gemacht:

- P is natürlich keine Teilmenge von NPC (sonst wäre P = NP = NPC)
Richtig ist, dass P Teilmenge von NP ist, und NP Teilmenge von EXP ist

- es gilt s \/ t1 /\ t2 === (s \/ t1) /\ (s \/ t2) (an der Tafel waren rechts Konjunktion und Disjunktion vertauscht.

Kevin Wayne, Princeton, hat gute Folien zu NP-Completeness:
http://www.cs.princeton.edu/~wayne/cs42 ... te-4up.pdf

Robert Sedgewick und Kevin Wayne haben schöne Folien zu "3SAT P-reduziert auf 3Color":
http://www.cs.princeton.edu/courses/arc ... ctions.pdf