4
$\begingroup$

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?

$\endgroup$
  • 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$ – Suresh Venkat Apr 13 '12 at 19:52
  • $\begingroup$ I hope the question is posed better now. $\endgroup$ – Willem Van Onsem Apr 15 '12 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.