For reference, the version of the nondeterministic time hierarchy theorem in question is this one:


The relevant portion of the proof in question (also from Arora-Barak) is here:


Arora-Barak define a NDTM as identical to a deterministic TM except that NDTMs have two transition functions such that either may chosen nondeterministically and used at each time step. However, the definition of a a NDTM with which I am more familiar is more in the flavor of Goldreich's text, which instead defines a transition relation, allowing more than two nondeterministic choices to be made at each time step.

My question is: how can the above proof be modified to work for Goldreich's definition of a NDTM? All of the proofs I have found that rely on the Goldreich definition (including Goldreich's own proof) only prove the coarser, logarithmic version of the nondeterministic time hierarchy theorem. Despite the equivalence of these two definitions, I can't find a way to work around the reliance of the proof on claim that $M_i$ has $2^{(f(i) + 1)^{1.1}}$ branches of computation, which holds assuming that only two nondeterministic choices are possible at each time step.

At first I figured the proof could be modified to suit the Goldreich definition simply by changing the base 2 in $f(i+1) = 2^{(f(i) + 1)^{1.1}}$ to whatever the size of the state space of $M_i$ is (since this is an upper bound on how many branches of nondeterministic computation you can obtain at each time step). However, since $i$ can be arbitrarily large and each binary string represents some Turing machine (one of the assumptions made by Arora-Barak), it seems that state spaces can be arbitrarily large as well and bounding them isn't quite as simple as picking a constant base other than 2.

  • 1
    $\begingroup$ How about picking a base depending on $i$? $\endgroup$ Jun 14, 2019 at 18:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.