<p>In <a href="http://dl.acm.org/citation.cfm?id=758079" rel="nofollow">P.M.B. Vitányi, Relativized Obliviousness, MFCS'80 paper</a> 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.</p>

<p>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.</p>

<p>Furthermore the paper states that if we would recombine the alphabet into $k&#39;&lt;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&#39;$ 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.</p>

<p>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?</p>

CC BY-SA 3.0
2012-04-13T19:52:28.680Z
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?)
Suresh Venkat
CC BY-SA 3.0
2012-04-15T15:49:55.427Z
I hope the question is posed better now.
willeM_ Van Onsem
<cc.complexity-theory><turing-machines>
How is Cooks overlap argument applied in Vitányi's theorem?
willeM_ Van Onsem
# How is Cooks overlap argument applied in Vitányi's theorem?

(Asked by: username_0 on 2012-04-13)

In [P.M.B. Vitányi, Relativized Obliviousness, MFCS'80 paper](http://dl.acm.org/citation.cfm?id=758079) 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'

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?

**Tags:** cc.complexity-theory, turing-machines

> **Comments:**
> **username_1**: 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?)  
> **username_0**: I hope the question is posed better now.  

---

## 0 answers

