2nd Semester 2003/04: Project: Computational Complexity
- Instructors
- P.van Emde Boas, L.Torenvliet
- ECTS
- 6
- Description
Interested students should contact dr Leen Torenvliet (e-mail) before enrolling. Grading will be based on an essay written in week four.
Content:-
Week 1. NP-complete sets and structure
- Isomorphism: Berman-Hartmanis proof about polynomial cylinders and the conjecture
- Padding: Sets in NEXP-EXP or higher up give sparse sets in NP-P
- Sparse complete sets. Left-set technique of Ogihara-Watanabe
-
Week 2. Semi-Feasible computation.
- Basic stuff about semi recursive sets and translation to P-selective sets
- Connection with tally and sparse sets
- Polynomial size circuits and sparse sets; advice functions
-
Week 3. Complete sets and robustness.
- Question: what type of sets can you remove from which type of completeness while retaining complete sets.
Reference. Bin Fu 92, Buhrman-Torenvliet 93, Buhrman Torenvliet 2004.
- Question: what type of sets can you remove from which type of completeness while retaining complete sets.
-
Week 1. NP-complete sets and structure
- Organisation
- Verantwordelijk Docent: dr Peter van Emde Boas