Two Tapes are Better than One for Nondeterministic Machines
Pavol Ďuriš, Zvi Galil · SIAM Journal on Computing · 1984
It is known that k tapes are no better than two tapes for nondeterministic machines. We show here that two tapes are better than one. In fact, we show that two pushdown stores are better than one tape. Also, k tapes are no better than two for nondeterministic reversal-bounded machines; and we show that even two reversal-bounded pushdown stores are better than one reversal-bounded tape. We also show that for one-tape nondeterministic machines, unrestricted operation is better than reversal-bounded operation.