Relationships Between Nondeterministic and Deterministic Tape Complexities

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

About this paperEnglishTiếng Việt日本語beside Englishbeside Tiếng Việtbeside 日本語

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.

非确定性与确定性带复杂度之间的关系*

Walter J. Savitch

应用物理与信息科学系， 加利福尼亚大学圣迭戈分校，La Jolla，加利福尼亚州92037

收到日期：1969年8月29日

研究了在确定型图灵机上模拟非确定型带有界图灵机所需的存储量。结果包括以下内容：定理。若L(n)≥log⁡2nL(n) \geq \log_2 n，则非确定型L(n)L(n)-带有界图灵机可以由确定型[L(n)]2[L(n)]^2-带有界图灵机进行模拟。证明了非确定型机器的计算与某些迷宫的穿行相对应。利用这一对应关系，可以构造一个特定的集合，即所有可穿行迷宫的编码所组成的集合，使得如果存在任何能够区分非确定型带复杂度类与确定型带复杂度类的集合，那么该集合就是这样一个集合。

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.