2nd Semester 2006/07: Topics in Complexity Theory

Instructors

Leen Torenvliet
If you are interested in this project, please contact Leen by e-mail.

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.