Υπολογιστική Πολυπλοκότητα 23-24 (CEID_NY302)

Ύλη:

1. Ορισμοί: NP-Complete και NP-Hard
2. Θεώρημα Αναγωγής για Απόδειξη NP-Πληρότητας
3. Θεώρημα Cook-Levin
4. Αναγωγή από SAT σε 3SAT

Sipser σελ. 363-371 χωρίς την απόδειξη του Θεωρήματος Cook-Levin (Θεώρημα 7.30)

Υλικό:

Διαφάνειες σελ. 1-18

Αντίστοιχη διάλεξη μέσω zoom από το ακαδημαϊκό έτος 20-21. Προσοχή: το περιεχόμενο μπορεί να μη συμπίπτει ακριβώς με την αντίστοιχη διάλεξη στην αίθουσα.