*Οι αριθμοί των διαφανειών αναφέρονται στο printer friendly pdf ( https://courses.corelab.ntua.gr/pluginfile.php/9341/mod_folder/content/0/CC_Slides_Handouts_2023_01_16.pdf?forcedownload=1 ), που είναι συμπαγές.

Oracles and the Polynomial Hierarchy
- Papadimitriou [1]: Section 14.3 pp.339-343, Section 17.2, pp.424-429 (χωρίς την απόδειξη του θ. 17.12)
- Διαφάνειες: 95-115

Structure of NP
- Papadimitriou [1]: Sections 14.1, 14.2 (χωρίς τις αποδείξεις των θ. 14.2, 14.3)
- Arora-Barak [2]: Theorem 2.22 (Ch.2, p.57), Chapter 3 (Η απόδειξη του θ. Ladner είναι διαφορετική εδώ, μέσω padding!)
- Διαφάνειες: 118-147

Randomized Computation
- Arora-Barak [2]: Sections 7.1, 7.3, 7.4, 7.5 (όχι την απόδειξη του θ. 7.15 [Sipser-Gacs])
- Διαφάνειες: 149-173

Non-Uniform Complexity and Circuit Lower Bounds
- Arora-Barak [2]: Sections 6.1 - 6.7, 14.1, 14.2, 14.4, 23.1, 23.2
- Διαφάνειες: 175-205, 208-215, 219-220

Interactive Proofs
- Arora-Barak [2]: Sections 8.1, 8.2 (όχι τα 8.2.2, 8.2.3), 8.3 (όχι τα 8.3.2, 8.3.3), 8.4, 8.5
- Διαφάνειες: 222-237, 241, 243-244, 255-258

Pseudorandomness and Derandomization
- Arora-Barak [2]: Sections 20.1, 20.3, 20.4 (χωρίς τις αποδείξεις)
- Διαφάνειες: 260-267, 275-282

Η εξέταση θα γίνει με κλειστά βιβλία!