| Kursusnavn (dansk): | Avancerede emner inden for kompleksitetsteori og beregnelighed |
| Kursusnavn (engelsk): | Advanced topics in Computational Complexity |
| Semester: | Efterår 2004 |
| Udbydes under: | cand.it., internet- og softwareteknologi (int) |
| Omfang i ECTS: | 7,50 |
| Kursussprog: | Engelsk |
| Kursushjemmeside: | https://learnit.itu.dk |
| Min. antal deltagere: | 0 |
| Forventet antal deltagere: | 10 |
| Maks. antal deltagere: | 20 |
| Formelle forudsætninger: | The student should be familiar with the basics of logic and complexity theory, for
example as taught at ITU in the course Logic and Computability, Computational Complexity from a Programming Perspective (DIKU), or equivalent. At the very least the student should be willing to catch up on this material as we go along.
A corresponding level of mathematical maturity is also required. |
| Læringsmål: | The objective of the course is to study further methods and results in computational
complexity theory.
After the course, the successful student
- have acquired knowledge of important complexity-theoretic techniques
- is able to work with several different computation models
- characterize various complexity classes,
- is able to construct oracles separating complexity classes
- is able to collapse complexity-theoretic hierarchies under various assumptions
- is able to produce certificates without giving away secrets
- appreciates the power of interactive computation
|
| Fagligt indhold: | Building on the knowledge
of basic complexity classs and relations between them, we plan to study, among other topics,
- oracle computations
- the polynomial-time hierarchy
- the graph isomorphism problem
- the non-solvable group method
- the random restriction method
- characterizations of complexity classes by function algebras
- one-way functions
- zero-knowledge proofs
- interactive protocols
|
| Læringsaktiviteter: | 3×45 minutes a week worth of freely interleaved presentations including those by (PhD) students, discussions, and exercises.
NB! In the introductory week, meaning from 27 August to 2 September 2004, exercises from 13:00 to 16:00 are cancelled. This means, that there will be only lectures from 9:00 to 12:00
|
| Eksamensform og -beskrivelse: | X. experimental examination form (7-scale; external exam), 13-skala, Ekstern censur The written work to be handed in can, by agreement with the student, be a careful exposition of the material of the student\'s presentation, an elaboration of one or more results from or adjacent to the material course, or solutions to a collection of problems.
Written works have to be handed in Friday 19 November 2004 12:00 am at the Examination Office.
|
| Litteratur udover forskningsartikler: | There is no single textbook for this course.
The students will be supplied with relevant photocopies.
Those seeking to invest in complexity-theoretic literature are
advised to have a look at C.H. Papadimitriou. Computational Complexity.
Addison-Wesley, 1994. ISBN 0-201-53082-1 (the first half covers the prerequisites and is assumed to be more or less
known, and the second half will serve as source for some of our topics), and the more advanced
L.A.Hemaspaandra & M.Ogihara.
The Complexity Theory Companion.
Springer, 2002. ISBN 3-540-67419-5, and
Ding-Zhu Du & Ker-I Ko.
Theory of Computational Complexity.
John Wiley & Sons, 2000. ISBN 0-471-34506-7. |
| | |
Kursusoversigt