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

Ύλη:

1. Κλειστότητα Κλάσεων P και NP ως προς Συγκεκριμένες Πράξεις

2. Απεικονιστικές Αναγωγές Πολυωνυμικού Χρόνου

3. Αναγωγή στην Κλάση P

Sipser σελ. 357-360

Υλικό:

Διαφάνειες σελ. 39-41, 47-50

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

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