Relationships Between Nondeterministic and Deterministic Tape Complexities

Walter J. Savitch, 1970, Journal of Computer and System Sciences

About this paperTiếng Việt中文

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

日本語
English

非決定性テープ計算量と決定性テープ計算量の関係*

Walter J. Savitch

応用物理学・情報科学部門 カリフォルニア大学サンディエゴ校、ラホヤ、カリフォルニア州 92037

1969年8月29日受理

決定性チューリング機械上で非決定性テープ制限チューリング機械をシミュレートするために必要な記憶容量について考察する。結果には次のものが含まれる。定理。L(n)≥log⁡2nL(n) \geq \log_2 nであるとき、非決定性のL(n)L(n)-テープ制限チューリング機械は、決定性の[L(n)]2[L(n)]^2-テープ制限チューリング機械によってシミュレートできる。非決定性機械の計算は、ある種の迷路の通り抜けに対応することが示される。この対応を用いて、通り抜け可能な迷路のすべての符号化の集合という特定の集合を構成する。すなわち、非決定性テープ計算量クラスと決定性テープ計算量クラスを区別する集合が存在するならば、この集合もそのような集合の一つである。

Department of Applied Physics and Information Science, University of California, San Diego, La Jolla, California 92037

Received August 29, 1969

The amount of storage needed to simulate a nondeterministic tape bounded Turing machine on a deterministic Turing machine is investigated. Results include the following: Theorem. A nondeterministic L(n)L(n)-tape bounded Turing machine can be simulated by a deterministic [L(n)]2[L(n)]^2-tape bounded Turing machine, provided L(n)≥log⁡2nL(n) \geq \log_2 n. Computations of nondeterministic machines are shown to correspond to threadings of certain mazes. This correspondence is used to produce a specific set, namely the set of all codings of threadable mazes, such that, if there is any set which distinguishes nondeterministic tape complexity classes from deterministic tape complexity classes, then this is one such set.

This section is missing here.

Introduction

This section is missing here.

Acknowledgments

References

  1. M. Blum, A machine-independent theory of the complexity of recursive functions, J. Assoc. Comput. Mach. 14 (1967), 322–336.
  2. A. Cobham, “The Recognition Problem for the Set of Perfect Squares.” IEEE Conference Record of the Seventh Annual Symposium on Switching and Automata Theory, Berkeley, Calif., 1966, pp. 78–87.
  3. J. E. Hopcroft and J. D. Ullman, “Formal Languages and Their Relation to Automata.” Addison-Wesley, Reading, Mass., 1969.
  4. J. E. Hopcroft and J. D. Ullman, Relations between time and tape complexities. J. Assoc. Comput. Mach. 15 (1968), 414–427.
  5. S. Y. Kuroda, Classes of languages and linear-bound automata. Information and Control 7 (1964), 207–223. (The relevant material also appears in [3], pp. 115–119.)
  6. P. S. Landweber, Three theorems on phrase structure grammars of type 1. Information and Control 6 (1963), 131–136. (The relevant material also appears in [3], pp. 115–119.)
  7. P. M. Lewis II, R. E. Stearns, and J. Hartmanis, “Memory Bounds for the Recognition of Context-Free and Context-Sensitive Languages.” IEEE Conference Record on Switching Circuit Theory and Logical Design, Ann Arbor, Mich., 1965, pp. 191–202. (The relevant material also appears in [3], pp. 162–164.)
  8. E. M. McCreight and A. R. Meyer, “Classes of Computable Functions Defined by Bounds on Computation: Preliminary Report.” Conference Record of ACM Symposium on Theory of Computing, Marina del Rey, Calif., May 1969, pp. 79–88.
  9. W. J. Savitch, “Deterministic Simulation of Non-deterministic Turing Machines (Detailed Abstract). Conference Record of ACM Symposium on Theory of Computing, Marina del Rey, Calif., May 1969, pp. 247–248.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into 日本語 by gpt-5, against glossary version 6. Translated from the English.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8.