Theorem 1. For every two real numbers there exists a rational number , such that .

Proof: We will consider 3 cases. First, suppose that , then .

Now, suppose that , then 0 is the rational number between and .

If apply case 1.    Q.E.D.

Theorem 2.  For every two real numbers there is an irrational number r, such that .
Proof: Since we have . If we now apply Theorem 1, we know there exists a rational number such that and thus . Obviously is irrational. Q.E.D.

The main topics for my bachelor thesis were

• The polynomial hierarchy and alternations;
• Randomized computation;
• Interactive proofs;
• Cryptography from a computational complexity point of view.

Before I started with my thesis I wanted to cover the PCP theorem instead of cryptography. However, due to time constraints I was forced to pick cryptography.

I will not post my thesis on this blog, since it contains solutions to many exercises of the book: Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak (see http://www.cs.princeton.edu/theory/complexity/).

Anyway, the new academic year already started a while ago and the first semester exams already passed by. In this first semester  I started with my master thesis under supervision of Professor Jan Van den Bussche. My thesis is about understanding the power of several kinds of navigational queries on graphs. At the moment I am working myself through this paper, trying to prove and workout all `missing’ details.

In the next blog post, which I hopefully will not forget to write, I will talk about what I  have already covered in my thesis up until this point.

I learned about several interesting topics:

• Oblivious simulation of a Turing machine only introduces a quadratic slowdown
• PSPACE completeness of TBQF (something we skipped during our Computational complexity course)
• LADNERS theorem: when then there exist languages that are not in P and not NP-complete.
• The polynomial hierarchy is a generalization of coNP and NP, I proved that if two levels of the hierarchy are equal, then the hierarchy collapses. I also learned that the polynomial hierarchy can also be defined using oracles and alternating Turing machines

I am currently reading about randomized computation.

The subject of my bachelor thesis will be: Advanced topics in Computational Complexity.
The topics will be:

• The polynomial hierarchy and alternations
• Randomized computation
• Interactive proofs
• PCP theorem and hardness of approximation
• (optional) Cryptography

I really want to thank my advisor Prof. Dr. Frank Neven, who spend a lot of time helping me select very interesting topics for this thesis.

I will post my progress on this thesis here and hope you will find it as interesting as I do.