Projects in Previous Years

2nd Semester 2003/04: Project: Computational Complexity

P.van Emde Boas, L.Torenvliet

Interested students should contact dr Leen Torenvliet (e-mail) before enrolling. Grading will be based on an essay written in week four.

  • 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.
Verantwordelijk Docent: dr Peter van Emde Boas