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

Ύλη:

1. Γραμμικώς Φραγμένο Αυτόματο (LBA)
2. Η Γλώσσα ΑΠΟΔΟΧΗ_{LBA} είναι διαγνώσιμη
3. Η Γλώσσα ΚΕΝΟΤΗΤΑ_{LBA} είναι μη- διαγνώσιμη με αναγωγή μέσω υπολογιστικού χρονικού
4. Απεικονιστικές Αναγωγές

Sipser σελ. 260-266, 276-281

Υλικό:

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

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