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?

Improve this question
$\endgroup$
2
  • 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, 2012 at 19:52
  • $\begingroup$ I hope the question is posed better now. $\endgroup$
    – willeM_ Van Onsem
    Apr 15, 2012 at 15:49

0

Reset to default

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.