Skip to content

Yogi Berra and Complexity Theory

January 30, 2011

More on a recent result on BQP and nondeterministic exponential time

Yogi Berra is a famous baseball player, who is probably better known for famous quotes than his stellar career. His quotes naturally fall into two categories: those that he said and those that he did not say. There is a book with the title: “I really didn’t say everything I said.”

Today Ken and I thought we would highlight a recent discussion that contains a result about quantum computation and its relationship to classical computation.

As Yogi has said: “It’s déjà vu all over again.” One reason we thought it would be okay to re-state the result is that we now are pretty sure that it is correct, and a paper is due out shortly. The work is joint with Ken and Atri. Another reason is that it builds and uses the framework of Ryan Williams’ recent result on his {\mathsf{ACC}} circuit lower bound on nondeterministic exponential time. A prediction:

Ryan’s framework for his proof will yield further insights into the structure of computation.

A second reason, though, is that our planned post “blew up”: We made too many wrong mistakes. Computer science may be 90% mental, but the other half is physical, and after a pitchy week we needed a rest. Even Napoleon had his Watergate. If the world was perfect, it wouldn’t be. In theory there is no difference between theory and practice, but in practice there is. Now it’s true that there are some people who, if they don’t already know, you can’t tell ’em—but though we thought we knew, we asked someone else just to be sure, and he found the bug. As a field we have deep depth. The moral is that you’ve got to be very careful if you don’t know where you are going, because you might not get there. (See this for the eight adapted Yogi Berra quotes in this paragraph and others in this introduction.)

Well when you come to a fork in the road, you should take it, so we’ll talk about both the above result and the broken idea. We’ll sketch our current proof of the result. Of course it might still have a bug, which would make this déjà vu all over again {\dots}

Quantum vs Nondeterministic

The theorem we are restating is:

Theorem: At least one of the following is true:


  1. The class {\mathsf{BQTIME}[t(n)]} is not contained in {\mathsf{NTIME}(t(n)^{1.99})}.
  2. The class {\mathsf{NTIME}[2^n]} is not contained in circuits of polynomial size.

Here {t(n)} is a time constructible function: that means that given {1^n} the value {1^{t(n)}} can be constructed in time {t(n)} by a deterministic Turing machine.

This theorem is interesting, we believe, for two reasons. For one it relates quantum computation directly to classical computation. Most would not be surprised to see that {\mathsf{BQTIME}[t(n)]} is not contained in even {\mathsf{NP}}, or even not in the polynomial hierarchy. But we cannot prove that, so showing even that it is not contained in {\mathsf{NTIME}[t(n)^{1.99}]} seems exciting. Of course the above theorem cannot establish even that. It does show that a consequence of the failure of this containment would be a result we believe, namely {\mathsf{NE} \not\subset \mathsf{P/poly}}, but one that is probably also very hard to resolve.

The point is that you prove what you can. We would have preferred to prove one of the statements of the theorem, not their disjunction. Perhaps someone will be able to in the near future, or perhaps not. Thus we’re left with a fork in the road, but we’ll take it.

Proof Sketch

The proof sketch requires some knowledge of Ryan Williams’ technique. Ken has adapted it from his comment here.

Assume for sake of contradiction that the theorem is false, i.e. that {\mathsf{BQTIME[t(n)]}} is in {\mathsf{NTIME[t(n)^{1.99}]}} and {\mathsf{NE}} is in {\mathsf{P/poly}}, for natural constructible time bounds {t(n)} we will quantify later. The goal is, given an arbitrary {2^n}-time nondeterministic Turing machine {N}, to simulate {N} on any {x} in {2^n/\mathsf{poly}(n)} nondeterministic time, violating the {\mathsf{NTIME}} hierarchy theorem. Define:


  1. {D_x} stands for a succinct representation of clauses {C_1 \wedge \dots \wedge C_m} that are satisfiable iff {N} accepts {x}. {D_x} is a circuit that on input {j} outputs the three indices {i_1,i_2,i_3} of variables in {C_j}, with their signs.
  2. {W_x} stands for a poly-sized witness circuit that takes the index {i} of a variable, and for some satisfying assignment independent of {i}, outputs the value of {x_i}. Under {\mathsf{NE} \subset \mathsf{P/poly}}, Williams’ adaptation of Impagliazzo Kabanets Wigderson’s easy-witness construction shows that whenever {x \in L(N)}, such a {W_x} exists.
  3. {\mathsf{WIT} = \{[x, D_x, W_x]:} for each {j}, {D_x(j) = \{i_1,i_2,i_3\}} is such that one of {W_x(i_1)}, {W_x(i_2)}, or {W_x(i_3)} satisfies {C_j\}}. (Note the condition entails {W_x} is a witness circuit and puts {\mathsf{WIT}} into {\mathsf{co-NP}}.)

Along lines of Williams’ paper, one can take {c} such that {D_x} and {W_x} have encoding size {n^c}; for {D_x} we can get {c \leq 10}, but for {W_x} the value of {c} depends on the application of IKW. We can put {r \simeq n^c} as the size of instances of {\mathsf{WIT}}. Now we have {\mathsf{WIT} \in \mathsf{co}-\mathsf{NTIME}[O(r)]} by Williams’ construction (as a side note, this implies {\mathsf{WIT} \in \mathsf{co}-\mathsf{NTIME}[r]} sharply by the Book-Greibach theorem). Moreover, his construction does this with only {n+O(log n) = O(r^{1/c})} bits of nondeterminism.

This means that the exhaustive search is over a domain of size {\mathsf{poly}(n)2^n} sharply. Thus applying Grover’s algorithm,

{\mathsf{WIT}} needs a {\mathsf{poly}(n)2^n} search {\implies} {\mathsf{WIT} \in \mathsf{BQTIME}[poly(n)2^{n/2}]}.

Now assume {\mathsf{BQTIME}[t(n)] \subseteq \mathsf{NTIME}[t(n)^{1.99}]}. Specifically we are applying this with {t(n) = \mathsf{poly}(n)2^{n/2}}, or more precisely in terms of the actual input length {r} to {\mathsf{WIT}}, with {t(r) = \mathsf{poly}(r)2^{r^{1/c}/2}}. However, since padding translates upward for quantum just as well as classical, we could start with any lower natural {t(n)} or {t(r)}. Thus {\mathsf{WIT}} is in {\mathsf{NTIME}[poly(n)2^{(1.99/2)n}= \mathsf{NTIME}[poly(n)2^n/2^{0.005n} ]}.

Here the terms in {r} and the fact that the input to {\mathsf{WIT}} has length {r} not {n} get absorbed into the {\mathsf{poly}(n)}. Now we finally get the algorithm:


  1. On input {x}, construct the circuit {D_x}. (poly-time)
  2. Using the hypothesis {\mathsf{NE} \subset \mathsf{P/poly}}, construct the “easy witness” circuit {W_x}. (subexp time)
  3. Build the uniform Grover circuits for {\mathsf{WIT}}.
  4. Since we are treating the circuits as uniform, there is a fixed nondeterministic Turing machine {N'} that runs in time {2^{n-0.005n}\cdot\mathsf{poly}} and accepts {\mathsf{WIT}}.
  5. So run {N'} on input {[x, D_x, W_x]}, and accept iff it accepts.

This gives {\mathsf{NTIME}[2^n] \subseteq \mathsf{NTIME}[2^{n - 0.005n}*\mathsf{poly}]}, a contradiction.

So we have: {\mathsf{BQTIME}[t(n)]} is not in {\mathsf{NTIME}[t(n)^{1.99}] \implies \mathsf{NE}} is not in {\mathsf{P/poly}}.

The Other Idea and Its Error

I decided I will tell you about the cool idea that blew up—at least a bit. Ken and I thought we had proof of the following theorem:

“Theorem”: For any reasonable time constructible function {t(n)} at most {2^{O(n)}},

\displaystyle  \mathsf{DTIME}[t(n)] \neq \mathsf{NTIME}[t(n)].

The “proof” was clever; it was based on the great previous work of Wolfgang Paul, Nick Pippenger, Endre Szemerédi and William Trotter, but used what we thought was a new trick. As we started to write up the proof up we circulated it to Rahul Santhanam, who kindly read it and noticed the mistake—which was taking for granted that alternating-machine based hierarchies based on fixed rather than “poly” time bounds would still have the downward-collapse property.

I learned several things from this failure that I want to share.

{\bullet } Write it up carefully: We spent a lot of time writing the proof up very carefully—indeed Ken “re-arranged” the paper twice while also dealing with a breaking news story. If we had not done this I think the error would have been very hard to spot.

{\bullet } Show the write-up to world experts: Santhanam knows more about this area than I do. He was able to spot the error very quickly, which saved us from spending more time on a broken idea. It also stopped us from telling others a result that was not proved.

{\bullet } Errors are in the “obvious steps”: I know this. I know this. I know this {\dots} But “…déjà vu again.” I know that the likely place that can go wrong in any proof is the part where you say: {\dots} is well known to be true. This is essentially where our mistake was—in a lemma that we just stated because it was so obvious. The detailed neat part of the proof is well written, easy to follow, and correct. The “this is well known” part was wrong—more exactly as Santhanam kindly said, it is open. We have contacted another expert in this area and might try to repair it. As Yogi Berra said, “It ain’t over till it’s over.”

Open Problems

The main technical question is: can we prove stronger results about the relationship of quantum computation and classic computation complexity classes? The other question is how can we avoid errors? I knew this but forgot: always check the parts of the “proof” that you think are “obvious.” They may not be.


[clarified “Yogi Berra” quotes; fixed typos]

7 Comments leave one →
  1. Editor permalink
    January 31, 2011 8:37 am

    In part 2 of the “Proof Sketch” section, “sch” should be “such”.

    The name “Szemer{é}di” should not contain the braces.

  2. January 31, 2011 11:47 pm


  3. A fan of your blog. permalink
    February 1, 2011 1:57 pm

    Prof. Lipton,

    I find it quite fascinating how you link the technical subject matter of each post to a person and their quotes/doings. This post, I particularly enjoyed, what with all the quotes from Yogi Berra. How you write such imaginative and technical posts multiple times each week is beyond me. But it entices me to check your blog every day for new entries!

    Anonymous reader.

  4. Sasho permalink
    February 1, 2011 2:07 pm

    Does the unproven lemma imply your result without your clever trick? I take it that it does not, so you might still have an interesting conditional result, even though you wanted a groundbreaking unconditional result. Ryan’s breakthrough came from reducing circuit lower bounds (hard to think about) to the algorithmic question of designing subexp algorithms for circtuit-sat (easier to think about?). Maybe your lemma is easier to think about in a similar way?


  1. Tweets that mention Yogi Berra and Complexity Theory « Gödel’s Lost Letter and P=NP --
  2. Cardinality of the set of all strings | cartesian product
  3. Succinct Constant Depth Arithmetic Circuits Are Weak « Gödel’s Lost Letter and P=NP

Leave a Reply to A fan of your blog. Cancel reply

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

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

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: