My bachelor thesis: Barriers to proving P != NP

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

Abstract:

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.

Advertisements
Explore posts in the same categories: Uncategorized

Tags: , , ,

You can comment below, or link to this permanent URL from your own site.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: