Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space
- 1 July 1990
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 37 (3) , 674-687
- https://doi.org/10.1145/79147.214070
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 σ solves the problem in time n 1+τ if σ + 2τ < 1/2.Keywords
This publication has 3 references indexed in Scilit:
- Lower bounds for recognizing small cliques on CRCW PRAM'sDiscrete Applied Mathematics, 1990
- A Natural NP-Complete Problem with a Nontrivial Lower BoundSIAM Journal on Computing, 1988
- A time-space tradeoff for language recognitionTheory of Computing Systems, 1984