Dimitri Surinx

When making exercises I had to prove that and are both dense in with the usual topology. To do this I had to make use of the following two theorems, which to me were quite remarkable, even though they were simple to prove.

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

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

Now, suppose that . Case one tells us that there is a rational number , such that , but .

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.

Last year I wanted to use this blog to post about the progress of my bachelor thesis. However, unfortunately after I made the first two posts I completely forgot about posting my progress. So, let me now summarize what I did do for my thesis last year.

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.

Last week I had the second meeting with my advisor Prof. dr. Frank Neven, this time I had to explain to him what I had learned in the last couple of weeks.

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.

Time flies by so quickly, the day I started studying at Hasselt University seems just like yesterday, while I already finished my first semester of my third bachelor year. Last week, the second semester of my third bachelor started. In this semester I have to write my bachelor thesis.

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.