An observation on time-storage trade off

ABSTRACT

Recently there have been several attempts to prove that every set of strings in @@@@ (i.e., recognizable in deterministic polynomial time) can be recognized in deterministic storage (log n)2. The methods used in the attempts were based on that of [1], in which it is shown that every context free language can be accepted in storage (log n)2 Our thesis in the present paper is that these attempts must fail. We define a specific set SP of strings which is clearly in @@@@, but in a certain well-defined sense cannot be recognized in storage (log n)2 using the techniques in [1]. We conjecture that no Turing machine recognizes SP within storage (log n)2, and show that if this conjecture is false, then in fact every member of @@@@ can be recognized within storage (log n)2.

REFERENCES

• 1: 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 1965 Symposium on Switching Circuit Theory and Logical Design.
• 2: Stephen A. Cook, Path systems and language recognition, Proceedings of the second annual ACM symposium on Theory of computing, p.70-72, May 04-06, 1970, Northampton, Massachusetts, United States [doi>10.1145/800161.805151]
• 3: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 4: Stephen A. Cook, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal of the ACM (JACM), v.18 n.1, p.4-18, Jan. 1971 [doi>10.1145/321623.321625]
• 5: M. S. Paterson and C. E. Hewitt, "Comparative Schematology", Record of Project MAC Conference on Concurrent Systems and Parallel Computation (June, 1970), 119-128, ACM, New Jersey (December, 1970).
• 6: S. A. Walker , H. R. Strong, Characterizations of flowchartable recursions short version, Proceedings of the fourth annual ACM symposium on Theory of computing, p.18-34, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804893]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Complexity of proof procedures

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.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)

General Terms:
Languages, Management, Theory