Weekly outline

• Χειμερινό Εξάμηνο 2024-2025
  

  Χειμερινό Εξάμηνο 2024-2025

  Προσφέρεται ως "Υπολογιστική Πολυπλοκότητα" στην ΣΗΜΜΥ.
  

  Διδάσκοντες:

  • Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
  • Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)
  • Αντώνης Αντωνόπουλος, συνεργαζόμενος ερευνητής (aanton@corelab.ntua.gr)

  
  

  Βοηθοί Διδασκαλίας:

  • Σταύρος Πετσαλάκης, Υ/Δ (spetsalakis@corelab.ntua.gr)

  
  

  Διαλέξεις:

  • Δευτέρα 17:00-20:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)
  • Πέμπτη 15:00-17:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)
    

  
  

       Έναρξη μαθημάτων: 7/10/24

  
  

  
  

  Περιεχόμενο Μαθήματος:

  Basic notions and results in Complexity Theory. Oracles & The Polynomial Hierarchy. The structure of NP. Randomized Computation. Non-Uniform Complexity. Circuit Lower Bounds. Interactive Proofs. Probabilistically Checkable Proofs. Pseudorandomness and Derandomization of Complexity Classes. Circuit Lower Bounds for NEXP. Counting Complexity. A short introduction to Fine-Grained Complexity.
  

  
  
  

  • Ανακοινώσεις Forum
  • Βιβλιογραφία - Υλικό - Σύνδεσμοι Page
  • Lecture Slides Folder
• Εβδομάδα 1
  

  Εβδομάδα 1

  Δευτέρα 7 Οκτωβρίου

  • Basic notions and results of Complexity Theory: Problems, Turing Machines and their properties, Undecidability and Rice's Theorem.

  
  

  Πέμπτη 10 Οκτωβρίου

  • Basic notions and results of Complexity Theory: Complexity Measures, Complexity Classes, Hierarchy Theorems. 

  
  

  Μπορείτε να διαβάσετε:
  

  • Ch. 1,2,3 from [1]
  • Ch. 0,1 from [2]
    

  Δείτε επίσης:
  

  • Στην υποσελίδα "Βιβλιογραφία-Υλικό-Σύνδεσμοι" θα βρείτε τις αναφορές για την βιβλιογραφία ([1], [2]), άλλες πηγές και σημειώσεις διαλέξεων, online courses Πολυπλοκότητας και άλλο ενδιαφέρον υλικό.