Archive for June 2011

My bachelor thesis: Barriers to proving P != NP

June 11, 2011

I have just finish my bachelor thesis Barriers to proving P != NP. I hope that some of you will find it interesting.


This thesis is about the \text{P} \stackrel{?}{=}\text{NP} problem and why this is so difficult to solve. We consider two different techniques from complexity theory, see how they can be used to separate complexity classes and why they do not seem to be strong enough to prove \text{P}\neq \text{NP}. The first technique is diagonalization, which we will use to prove the time hierarchy theorem. We will then see why a result of Baker, Gill and Solovay seems to indicate that this technique cannot prove \text{P}\neq \text{NP}. We will see how the circuit model can be use to prove PARITY\notin AC^0 and see a result by Razborov and Rudich, which indicate that this approach is also too weak to prove \text{P}\neq\text{NP}. Finally, we will see that provability and computability are closely related concepts and show some independence results.

Not abstract:

I wish I had had enough time to include algebrization.