Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines
✍ Scribed by Martin Sauerhoff
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 258 KB
- Volume
- 66
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
It is well known that a nondeterministic Turing machine can be simulated in polynomial time by a so-called guess-and-verify machine. It is an open question whether an analogous simulation exists in the context of space-bounded computation. In this paper, a negative answer to this question is given for ordered binary decision diagrams (OBDDs) and one-way Turing machines. If it is required that all nondeterministic guesses occur at the beginning of the computation, this can blow up the space complexity exponentially in the input length for these models. This is a consequence of the following main result of the paper. There is a sequence of boolean functions f n : f0; 1g n -f0; 1g such that f n has nondeterministic OBDDs of polynomial size that use at most ð1=3Þ Á ðn=3Þ 1=3 log n Á ð1 þ oð1ÞÞ nondeterministic guesses for each computation, but f n already requires exponential size if only at most ð1 À eÞ Á ð1=3Þ Á ðn=3Þ 1=3 log n nondeterministic guesses may be used, where e40 is an arbitrarily small constant.