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

Access Restriction
Subscribed

 Author Gurevich, Yuri Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1990 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science 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, butno deterministic machine (in a very general use of this term) with sequential-access input tape and work space $\textit{n}&sgr;$ solves the problem in time $\textit{n}1+τ$ if &sgr; + 2τ < 1/2. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1990-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 37 Issue Number 3 Page Count 14 Starting Page 674 Ending Page 687

#### Open content in new tab

Source: ACM Digital Library