A hierarchy for nondeterministic time complexity

ABSTRACT

The purpose of this paper is to prove the following result: Theorem 1 For any real numbers r1, r2, 1 ≤ r1 < r2, there is a set A of strings which has nondeterministic time complexity nr2 but not nondeterministic time complexity nr1 The computing devices are non-deterministic multitape Turing machines.

REFERENCES

• 1: Oscar H. Ibarra, A Note Concerning Nondeterministic Tape Complexities, Journal of the ACM (JACM), v.19 n.4, p.608-612, Oct. 1972 [doi>10.1145/321724.321727]
• 2: Walter Savitch. Relationships between nondeterministic and deterministic tapé complexities. J. Computer and System Sciences 4, pp 177-;92 (1970).
• 3: S. Ruby and P. C. Fischer. Translational methods in computational complexity. 1965 IEEE Conference Record on Switching, Circuit Theory, and Logical Design - Sixth Annual Symposium, pp. 173-;78.
• 4: F. C. Hennie , R. E. Stearns, Two-Tape Simulation of Multitape Turing Machines, Journal of the ACM (JACM), v.13 n.4, p.533-546, Oct. 1966 [doi>10.1145/321356.321362]
• 5: A. R. Meyer, A. L. Rosenberg, and P. C. Fischer. Multi-tape simulation of multi-head Turing machines, IEEE Conference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory, 117-;27.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Alternation and nondeterminism

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)
      F.1.3 Complexity Measures and Classes
          Subjects: Complexity hierarchies
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Proof theory

General Terms:
Theory