Letzte Vorlesung, Fehler und Folien

Generelle Diskussionen zu den Themen aus der Vorlesung

Letzte Vorlesung, Fehler und Folien

Beitragvon gert.smolka » 05 Feb 2014, 18:58

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
gert.smolka
 
Beiträge: 8
Registriert: 15 Okt 2013, 18:04

Zurück zu Vorlesung

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

cron