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

Καλησπέρα,

Μου ζητήθηκε να ανεβάσω την ύλη του μαθήματος στην eclass. Δεν έχω αποφασίσει ακόμη πλήρως το τι θα δούμε μέχρι και το τέλος του εξαμήνου.

Σε κάθε περίπτωση, μέχρι στιγμής έχουμε καλύψει από το βιβλίο του Sipser το Κ.7, χωρίς την απόδειξη του Θ. Cook-Levin. Θα δούμε σίγουρα και το Κ.8 και κάποιες επιλεγμένες παραγράφους από τα Κ.9 και ίσως και 10.

Τα μέρη Ι και ΙΙ  του βιβλίου του Sipser είναι εκτός ύλης. Στο Κεφ. 0 μπορείτε να ανατρέχετε ως μία πρώτη πηγή για πράγματα που θεωρούνται γνωστά και μπορεί να σας διαφεύγουν.

 Γιάννης