How Fast Can We Simulate Guessing?
A nondeterministic Turing machine can be simulated faster than searching its configuration graph
Subrahmanyam Kalyanasundaram is one of my current graduate students, and is working on various problems in complexity theory. He is—as I have said before—one of the reasons these discussions are half as coherent as they are. I have no idea what I would do without his help.
Today I want to make a short announcement about a paper Subruk, Ken Regan, Farbod Shokrieh, and I have finally written. The paper is on the problem: How fast can a nondeterministic Turing machine (NTM) be simulated by a deterministic Turing machine? I have discussed this problem before, and we now have a draft of the paper.
Besides stating our theorem I want to discuss some possible extensions and conjectures. When I was a beginning researcher I read most of Albert Meyer’s papers; they were always interesting and usually quite deep. I noticed Albert used the phrase “strong conjecture,” and I asked him one day what was the difference between a strong conjecture and a conjecture? He explained his papers had three types of statements:
- Theorems and Lemmas: These were statements he could prove.
- Conjectures: These were statements he believed were true, but could not prove.
- Strong Conjectures: These were statements he was sure were true, but did not have the time to work out all the details.
I think whenever Albert said “strong conjecture” he was always right.
A Sale: Off
I wish I could report we have a terrific result, a shockingly great simulation, but we do have a significant improvement over the best known simulations. Here is the main theorem—see the full paper for the details:
Theorem: Any -tape nondeterministic Turing machine with tape alphabet size that runs in time , can be simulated by a deterministic Turing machine in time
The theorem in the paper has a more precise bound, but the key information is all here. The whole point of this theorem is the factor in the exponent, a improvement over the known methods. I could have written the key expression as
The standard way to simulate a NTM yields : thus, we have improved the deterministic time by a square root. The usual method notes there are about
total configurations of a NTM running in time . These configurations form a natural directed graph of vertices, and so a deterministic simulation need only search this graph. Our theorem uses the special structure of this graph—it comes from a Turing machine—to reduce the search cost from to .
I will follow Albert Meyer and make two conjectures about our theorem. However, they are not strong conjectures, but I do think there is a good chance they are provable with our technology.
Conjecture Suppose is a -tape nondeterministic Turing machine with tape alphabet size that runs in time . Then, there is a deterministic Turing machine that runs in time
and computes the exact number of accepting computations of on a given input of length .
I think, along with my co-authors, our proof can be extended to handle computing the number of accepting computations, not just whether or not there is one. The reason it is only a conjecture and not a strong conjecture, is there are some subtle details that need to be carefully checked. Of course the interest in this result is the application to the simulation of other complexity classes such as #P and PP.
In a different direction I think we should be able to use the famous quantum algorithm of Lov Grover to prove the following:
Conjecture Any -tape nondeterministic Turing machine with tape alphabet size that runs in time , can be simulated by a quantum Turing machine in time
with bounded error probability.
Note, the exponent is half of the deterministic exponent. This is exactly what one would expect if Grover’s method can be applied here.
The obvious problem is to improve the main simulation, to decrease . Is it possible to prove a much better simulation? I think so. Perhaps can be any positive number. Also are either or both of the stated conjectures true? Are they strong conjectures?
P.S. Happy earth day.