Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space

ABSTRACT

A technique is developed for establishing lower bounds on the computational complexity of certain natural problems. The results have the form of time-space trade-off and exhibit the power of nondeterminism. In particular, a form of the clique problem is defined, and it is proved that: a nondeterministic log-space Turing machine solves the problem in linear time, but no deterministic machine (in a very general use of this term) with sequential-access input tape and work space n&sgr; solves the problem in time n1+&tgr; if &sgr; + 2&tgr; < 1/2.

REFERENCES

• 1: P. Beame, Lower bounds for recognizing small cliques on CRCW PRAM'S, Discrete Applied Mathematics, v.29 n.1, p.3-20, Nov. 1990 [doi>10.1016/0166-218X(90)90079-R]
• 2: BOLLOBAS, B. Random Graphs. Academic Press, London, 1985.
• 3: DURIS, P., AND GALIL, Z. A time-space tradeoff for language recognition. Math. Syst. Theory 17 (1984), 3-12.
• 4: Etienne Grandjean, A natural np-complete problem with a nontrivial lower bound, SIAM Journal on Computing, v.17 n.4, p.786-809, August 1988 [doi>10.1137/0217050]
• 5: KANNAN, R. Towards separating nondeterministic time from deterministic time. In Proceedings of the 22nd IEEE Conference on Foundations of Computer Science. IEEE, New York, 1981, pp. 235-243.
• 6: PAUL, W. J., PIPPENGER, N., SZEMEREDI, E., AND TROTTER, W.T. On determinism versus nondeterminism and related problems. In Proceedings of the 24th IEEE Symposium on Foundation of Computer Science (Tucson, Az., Nov.). IEEE, New York, 1983, pp. 429-438.
• 7: SPENCER, J. Ten lectures on the probabilistic method. CBMS-NSF Regional Conference Series in Applied Math., number 52, SIAM.
• 8: YAO, A.C. Near-optimal time-space tradeoff for element distinctness. In Proceedings of the 29th Symposium on Foundations of Computer Science. IEEE, Computer Society Press, Las Alamitos, Calif., 1988, pp. 91-97.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity measures

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); Automata (e.g., finite, push-down, resource-bounded)
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms; Counting problems
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Performance