Μάθημα : Υπολογιστική Πολυπλοκότητα

Ύλη:

1. Αναγωγές στην Υπολογισιμότητα
2. Απόδειξη με Αναγωγή ότι η γλώσσα ΤΕΡΜΑΤΙΣΜΟΣ είναι μη-διαγνώσιμη
3. Μη-Διαγνωσιμότητα του Προβλήματος ΚΕΝΟΤΗΤΑ
4. Μη-Διαγνωσιμότητα του Προβλήματος ΙΣΟΔΥΝΑΜΙΑ

Sipser σελ. 253-260

Υλικό:

Διαφάνειες σελ. 1-16, 25

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

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