ΘΕΩΡΗΤΙΚΗ ΠΛΗΡΟΦΟΡΙΚΗ Ι (ΣΗΜΜΥ)
ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ ΙΙ (ΜΠΛΑ)

ΕΞΕΤΑΣΤΕΑ ΥΛΗ ΜΑΘΗΜΑΤΟΣ
2014-2015

- Από το βιβλίο του Παπαδημητρίου [1]:

• Κεφ. 1 "Problems and Algorithms"
• Κεφ. 2 "Turing Machines": (όχι το section 2.6)
• Κεφ. 3 "Computability": (όχι η παράγραφος "Recursive Inseparability", σελ. 63-64)
• Κεφ. 4 "Boolean Logic" : μόνο 4.1, 4.2
• Κεφ. 5 "FO Logic" : μόνο 5.7
• Κεφ. 7 "Relations between CCs"
• Κεφ. 8 "Reductions and Completeness": (όχι την απόδειξη του θ. 8.3 [Fagin])
• Κεφ. 9 "NP-complete problems"
• Κεφ. 10 "coNP and function problems": (όχι το section 10.2)
• Κεφ. 14 "On P vs. NP": μόνο τα 14.1, 14.3
• Κεφ. 16 "Logarithmic Space": μόνο το 16.1
• Κεφ. 17: "The Polynomial Hierarchy": 17.1 (από το τέλος της σελ. 415 και μετά: "The classes P^NP και FP^NP"), 17.2 (χωρίς τις αποδείξεις των θ. 17.12 και 17.13)
• Κεφ. 18 "Computation that counts": (χωρίς τις αποδείξεις των θ. Valiant (18.3) και Valiant-Vazirani (18.6)) *
• Κεφ. 19 "Polynomial Space": μόνο το θ. 19.1
  (*μπορείτε να δείτε και την αντίστοιχη ύλη από το κεφ. 17 του Arora-Barak, αν το προτιμάτε)

- Από το βιβλίο των Arora-Barak [2]:

• Κεφ. 6 "Boolean Circuits": (χωρίς τις αποδείξεις των θ. 16.19 [Karp-Lipton], 6.20), όχι τα 6.5, 6.6, 6.8
• Κεφ. 7 "Randomized Computation" : μόνο τα 7.1, 7.3, 7.4, 7.5 (όχι την απόδειξη του θ. 715 [Sipser-Gacs])
• Κεφ. 8 "Interactive Proofs": όχι τα 8.2.2, 8.2.3, 8.3.2, 8.3.3, 8.6, 8.7
• Κεφ. 11 "PCP Theorem and Hardness of Approx": όχι τα 11.4, 11.5

- Οι διαφάνειες του μαθήματος (βρίσκονται εδώ)

- Οι σημειώσεις "Quantifier Characterizations of CCs" (βρίσκονται εδώ)