In P.M.B. Vitányi, Relativized Obliviousness, MFCS'80 paper one can read that the proof of Theorem 1 is based on the overlap-argument of Cook, however I don't see how this argument is applied.

The paper defines a language that is decided by a turing machine with $k$ stacks. The movements of those heads are the same for each disjunct pair in the alphabet (for instance equal for $a$ and $b$, for $c$ and $d$,...). The alphabet itself is the union of $k$ of those pairs.

Furthermore the paper states that if we would recombine the alphabet into $k'<k$ groups (and the head movements need to be the same for each element in the same group). It would not be possible to evaluate the language in linear time. I think thats because in that case it doesn't make sense to have more than $k'$ heads (because they should move the same, one could simply concatenate several stacks into one stack). Furthermore after some time the data in a stack will be spread resulting in additional complexity to look back in the stack.

The author however states that this can be proven with Cooks overlap argument. I don't see how this argument is applied in this case?

  • 2
    $\begingroup$ This is a very cryptically posed question. You might find more responses if you were able to provide some context (and what is Theorem 1?) $\endgroup$ Apr 13, 2012 at 19:52
  • $\begingroup$ I hope the question is posed better now. $\endgroup$ Apr 15, 2012 at 15:49


Your Answer

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