Bonyolultságelmélet eloadás - Complexity Theory Lecture

Péntek - Friday 12:00-13:30+ Déli Tömb 0-311 Konig terem

Hasznos linkek:

Eloadáshoz kapcsolódó legfrisebb jegyzet: .pdf Lecture notes: .pdf
Tavalyi eloadás - Last year: .html Régebbi - Older: .html
Gyakorlat - Exercises: Tamas
Alapveto bonyolultsági osztályok - Basic complexity classes: .html Turing-gép szimulátor: .html Gagyi játék - Simple game: .html
Ajánlott olvasmányok - Recommended books: Christos H. Papadimitriou: Számítási bonyolultság; Sanjeev Arora és Boaz Barak: Computational Complexity: A Modern Approach .html
Egyéb kapcsolódó ismeretterjeszto könyvek - Books for layman: Lance Fortnow: The Golden Ticket: P, NP, and the Search for the Impossible; Raymond Smullyan könyvek, pl.: To Mock a Mockingbird; Roger Penrose: A császár új elméje; Douglas L. Hofstadter: Gödel, Escher, Bach

Órák témái - Weekly topics:

(Ahol nem a jegyzetet követtük, ott van link.)
13. óra (dec. 13): Egyirányú függvények és Goldreich-Levin tétel, Impagliazzo világai.html, PPAD (wiki) és testvérei
12. óra (dec. 6): MAX-3SAT approximáció, PCP és approximálhatatlanság (14.6 és 14.7 fejezet), álvéletlen generátorok (7. fejezet)
11. óra (nov. 29): Valiant-Vazirani izolációs lemmával wiki, Polinomiális hierarchia és Sipser-Gács .html
10. óra (nov. 22): Arthur-Merlin AM-fejezet.pdf, Zero-knowledge proofs, Orákulumok
9. óra (nov. 15): Polyazonosság 0-1 értékü bemenetre: 14.4 fejezet, IP=PSPACE
8. óra (nov. 8): NL=co-NL wiki, TQBF wiki, GG wiki, jatekok bonyolultsaga.html
7. óra (okt. 25): Entrópia, Incompressibility method, incompress.ppt
6. óra (okt. 18): DET \in NC, Kolmogorov-bonyolultság, CLIQUE-re nincs monoton.pdf (érdeklodoknek)
5. óra (okt. 11): MAJORITY\notin AC0, PARITY-re vázlat.pdf (érdeklodoknek)
4. óra (okt. 4): Hálózatok, NC, Barrington wikipedia
3. óra (szept. 27): Nemdet kommunikációs bonyolultság, Karchmer-Wigderson survey.pdf cikk.pdf
2. óra (szept. 20): Nemdet döntési fák, kommunikációs bonyolultság
1. óra (szept. 13): Döntési fák