Teacher Teach Yourself

How teaching helps you understand proofs

Stanislav Žák is a theorist who has made important contributions to complexity theory. He was at the Institute for Computation Techniques of the Technical University in Prague thirty years ago when he proved the theorem below. He is now affiliated with the Institute of Computer Science of the Czech Academy of Sciences, where he has just written a new paper on “A Turing Machine Distance Hierarchy” with his colleague Jirı Šıma. He should not be confused with Professor Stanislaw Żak of Purdue’s ECE Department.

Today I want to discuss a classic theorem of Žák that is in the textbooks, and why it is a bit tricky to understand.

The power of the following theorem is in its statement, but the beauty is in its proof:

Theorem: Let and be constructible functions with . Then nondeterministic time Turing Machines that run in time compute more than those that run in time only .

In symbols,

Here is proper subset. An example of its power is that it separates nondeterministic time from time , which is much stronger than anything we can prove for deterministic time. This result uses a clever simulation of Ron Book and Sheila Greibach which I have discussed before.

Teaching

One of the side-effects of teaching is that when you present material you really have to know it perfectly. If your understanding is approximate, then it is hard to get students to completely understand. You may be able to fill the details in later, but at the board you’d better—in my experience—have it down exactly.

So to prepare for my class on the above theorem, I decided that the book’s proof was not that easy to follow. I decided to write the proof up in my own way. I hope this helps you understand the argument.

I hasten to add that there is nothing wrong or unclear about Žák’s proof. It was the rendition in the textbook that I found a bit unclear. Oh well.

Defining the Diagonal Machine

The goal is to diagonalize over NTMs that run in some polynomial time with another NTM that runs in a higher polynomial. The argument can be made much tighter, but I believe the slippery part of the argument is what I will focus on here.

Let’s start by picking a series of fast growing numbers

that we fix later. Rather than magically set them now, I prefer to delay their definition. Think of them as growing fast, and you will soon see that they need only satisfy two simple constraints.

Let’s now define a NTM that operates as follows. It diagonalizes only on inputs of the form —on other inputs we may simply say it accepts. On inputs of the form there are two cases depending on the relation of and the sequence of the ‘s. Thus the first requirement on the sequence is that itself can easily decide which of the following two cases holds.

Case I: In this case for some . Here simulates

for time, and then flips its answer. If the computation above does not halt it accepts; otherwise, it does the opposite. This is the diagonalization step. This can be done efficiently because is much larger than the input . This is the key:

How much larger? It must be exponentially larger so that can simulate the nondeterministic computation by a brute-force manner. Nothing clever here. Brute force. This is the second and last requirement on the sequence.

Case II: In this case is not equal to any of the ‘s. Then there is a unique so that

In this case just simulates for steps. This is not a typo—there may be some—but the exponent is really . This small point is critical to make it all work, as you will see it a moment.

That is the description of . It clearly is a NTM that runs in time . I am being loose with the polynomials, since they are not the tricky part.

Okay, as with any diagonalization proof, we now get to the key step where we show that some computation of must take on two distinct values, which is of course a contradiction. So we assume that itself can be computed by some NTM that runs too fast. We will then show that this leads to a contradiction.

Finishing the Proof

Still with me? We know that for some , —let’s call this assumption “A”. Let’s look at . This is the value of that will be inconsistent.

By case I, we know that (*)

This is not, I repeat not, a contradiction. Note that the exponents are different. But we have case II to exploit. We will now show that it implies that (*) is false, which is our desired contradiction.

These equalities imply that

But this is a contradiction with (*). Done.

The clever use of computing on input should now be clear. It allows the chain of equalities to work.

I hope this helps.

Open Problems

There are functions such that , but it is not true that . An example is , . Can we diagonalize—conveniently—in cases like that?

Finally Lance Fortnow and Rahul Santhanam in their paper have a newer way to prove this result—see their paper on “Robust Simulations and Significant Separations.”

Fixed picture thanks to Rostislav Horcik. Sorry for error.