Μάθημα : Υπολογιστική Πολυπλοκότητα
Κωδικός : MATH830
Ύλη μαθήματος για εξετάσεις Εαρινού και Σεπτεμβρίου 2025
Καλησπέρα σε όλα,
Η ύλη από το βιβλίο του Sipser, μέρος ΙΙΙ:
- Κ7, Χρονική Πολυπλοκότητα: όχι η παράγραφος 7.5 (Θ. Cook-Levin) και οτιδήποτε αναφέρεται σε αυτόματα, κανονικές γλώσσες και ασυμφραστικές γραμματικές
- Κ8, Χωρική Πολυπλοκότητα: όχι οι παράγραφοι 8.3.2-8.3.3, η απόδειξη της πληρότητας του TQBF και οτιδήποτε αναφέρεται σε αυτόματα, κανονικές γλώσσες και ασυμφραστικές γραμματικές.
Γ.