14
$\begingroup$

Is there a proof that the emulation of a Turing machine on an oblivious Turing machine can't be done in less than $\mathcal{O}\left(m\log m\right)$ where $m$ is the number of steps the Turing machine uses? Or is this just an upper bound?

In the paper of Paul Vitányi about relativized oblivious Turing machines, Vitányi claims

"They [Pippenger and Fischer, 1979] showed that this result cannot be improved in general, since there is a language L wich is recognized by a 1-tape real-time Turing machine $M$, and any oblivious Turing machine $M'$ recognizing $L$ must use at least an order $O(n \log n)$ steps".

This should state $O(m \log m)$ as an absolute bound. However I don't find any proof of this in

Pippenger, Nicholas; Fischer, Michael J., Relations among complexity measures, J. Assoc. Comput. Mach. 26, 361-381 (1979). ZBL0405.68041.

Any ideas? Furthermore, what is the space complexity of this emulation? As far as I know the conversion to a universal Turing machine only doubles the tape length. Can I assume that the space complexity is $\mathcal{O}\left(l\right)$ with $l$ the space complexity of the original Turing machine?

Improve this question
$\endgroup$
3
  • $\begingroup$ Please match parentheses and define what T is. I think that it is still open, but I am not an expert. $\endgroup$
    – Tsuyoshi Ito
    Commented Mar 11, 2012 at 23:17
  • 2
    $\begingroup$ what's an oblivious turing machine ? $\endgroup$
    – Suresh Venkat
    Commented Mar 12, 2012 at 2:22
  • 7
    $\begingroup$ An Oblivious Turing Machine is a Turing Machine where the movement of the heads only depends on the length of the input and not the input itself. For instance linear search (if the head keeps moving until it has reached the end of the input) $\endgroup$
    – willeM_ Van Onsem
    Commented Mar 12, 2012 at 2:42

2 Answers 2

Reset to default
20
$\begingroup$

As mentioned above, it is not known in general if there is a faster oblivious simulation.

But interesting lower bounds for this problem are known, under more constrained conditions. For instance, what if you want an oblivious simulation that preserves not only the time $t$ but also the space usage $s$? Beame and Machmouchi have recently proved an interesting time-space tradeoff lower bound for this problem: either the space must increase by a factor of $n^{1-o(1)}$, or the time must increase by a factor of $\Omega(\log n \cdot \log \log n)$.

The paper is here: http://eccc.hpi-web.de/report/2010/104/

Improve this answer
$\endgroup$
0
13
$\begingroup$

Just an extended comment: I think it is still an open problem; see Lipton and Regan's blog for some nice discussions about improving the result of the Fischer-Pippenger theorem.

For example see the posts: Oblivious Turing Machines and a "Crock" or Circuits Bounds for Turing Machine Computations (both dated 2009).

In the second post they show that a better circuit bound ( $O(n \log {\log n})$) is possible using a partial-boolean function $g:2^n \to \{0,1,*\}$ that approximates the original function $f$ on $2^{n-o(n)}$ inputs.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I've read the Fischer-Pippenger theorem and it's proof. However never in the proof there is a component that says that this there is no faster method. I was wondering if there exists a proof that says this is the guaranteed minimum. If you look at the proof they emulate the TM on a UTM and then perform a little hack to make it oblivious. However one can argue the first step is only necessary to know how the machine will behave. $\endgroup$
    – willeM_ Van Onsem
    Commented Mar 12, 2012 at 0:37
  • $\begingroup$ @CommuSoft No one is suggesting that the proof is anything but an upper bound proof. The blog posts suggest that improving on Fischer-Pippenger is an open problem. $\endgroup$
    – Sasho Nikolov
    Commented Mar 12, 2012 at 0:53
  • $\begingroup$ @CommuSoft: It is an open problem ... perhaps a faster method exists or someone will prove that it is the best achievable. $\endgroup$
    – Marzio De Biasi
    Commented Mar 12, 2012 at 0:58
  • $\begingroup$ Well I'm reading a paper published by Paul Vitányi called "Relativized Obliviousness" that seems to claim the time is at least O(m log m). However I'm not quite sure yet if it uses the Fischer-Pippenger theorem to proof this. $\endgroup$
    – willeM_ Van Onsem
    Commented Mar 12, 2012 at 1:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.