# 2nd Semester 2006/07: Topics in Complexity Theory

- Instructors
- ECTS
- 6
- Description
- Separating complexity classes, like
**P**and**NP**is the holy grail for complexity theory. Many attempts were made and failed. It seems that this problem is just too hard. Many methods fail because of relativization. Most machine based proofs should work just as well, when oracles are attached to the machines used in the proofs. Unfortunately for most complexity classes oracles exist that separate them as well as oracles that collapse them. A different approach is to look at the structure that is allowed for special subclasses. For instance,**P**allows sparse complete sets under polynomial time reductions, whereas**EXP**does not. Therefore**P**is not equal to**EXP**, but also if**NP**would allow sparse complete sets, then**NP**is not equal to**EXP**, and if**NP**would not allow sparse complete sets, then**P**is not equal to**NP**. In fact it can be shown that**NP**allowing sparse complete sets implies**P=NP**.Complete sets have a lot of structure. They sort of represent the entire complexity class through a reduction. A reduction and information about the complete set gives a decision algorithm for the set reduced from. There are, beyond sparseness, many structural properties a set might have. To name a few:

**P**-Selectivity, Small Circuits, Autoreducibility, Mitoticity and so on. Having or not having these structural properties has implications for the collapse or separation of complexity classes and are therefore worth studying. To name a single example: if the Turing complete sets in exponential space are auto reducible then**NL**is not equal to**NP**and if they are not then**PH**is not equal to**PSPACE**. Research on this topic started in the early nineties but was recently picked up and new results by Glasser et al. appeared.In this project we will study a collection of papers centered around the question "what are the structural properties that complete sets might have in certain complexity classes", starting with the old result on sparse complete sets in NP, working up to more recent results on autoreducibility and mitoticity. Ideally we find some new properties, but as a minimum case students write an essay on the papers studied to obtain credits.