Towards separating nondeterminism from determinism | Theory of Computing Systems Skip to main content
Springer Nature Link
Log in

Towards separating nondeterminism from determinism

  • Published:
Mathematical systems theory Aims and scope Submit manuscript

Abstract

The main result of this paper is a separation result: there is a positive integerk such that for all well-behaving functionst(n), there is a language accepted by a nondeterministic (multi-tape) Turing machine in timet(n) which cannot be accepting by any deterministic (multitape) Turing machine in timeO(t(n)) and simultaneously spaceo((t(n)) 1/k). This implies, for example that for any positive integer,l,l ≠k, there is a language accepted by an l time bounded NDTM which cannot be accepted by a DTM in time and spaceO(n l) andO((logn)l′) respectively for anyl′. Such a result is not provable by direct diagonalization because we do not have time to “simulate and do the opposite". We devise a different method for accomplishing the result: We first use an alternating Turing machine to speed up the simulation of a time and space bounded DTM and then argue that if our separation result did not hold, every NDTM can itself be simulated faster by another NDTM producing a contradiction to the standard hierarchy results. Some other applications of this method are also presented.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bruss, A. R. and Meyer, A. R., On time-space classes and their relation to the theory of real addition,Theoretical Computer Science 11 (1980), 59–69.

    Google Scholar 

  2. Chandra, A. K., Kozen, D. and Stockmeyer, L. J., Alternation,Journal of the ACM, 28, 1, January (1981), pp. 114–133.

    Google Scholar 

  3. Constable, R. L., Two types of hierarchy theorems for axiomatic complexity classes, InComputational Complexity, R. Rustin Ed., Algorithmics Press, N.Y., (1973), pp. 37–63.

    Google Scholar 

  4. Cook, S. A., Deterministic CFS's are accepted simultaneously in polynomial-time and log squared space,Proc. 11th Annual ACM Symposium on Theory of Computing, May (1979), pp. 338–345.

  5. Cook, S. A., A hierarchy for non-deterministic time complexity,Journal of Computer and System Sciences, 7 (1973), pp. 343–353.

    Google Scholar 

  6. Hartmanis and Stearns, R. E., On the computational complexity of algorithms,Trans. American Math. Society 117 (May 1965) pp. 590–607.

  7. Hopcroft, J., W. J. Paul and Valiant, L. J., On time versus space,JACM 24 (1977), 332–337.

    Google Scholar 

  8. Ibarra, O., A note concerning nondeterministic tape complexities,J. Assoc. for Computing Machinery 19 (1972).

  9. Meyer, A. R. and Stockmeyer, L. J., The equivalence problem for regular expressions with squaring requires exponential space,Proc. 13th IEEE Symposium on Switching and Automata Theory (1972), pp. 125–129.

  10. Paul, W. J., On time hierarchies,Proc. 9th Annual ACM Symposium on the Theory of Computing (1977), pp. 218–222.

  11. Paul, W. J., Prauss, E. J. and Reischuk, R., On alternation, 19th IEEE Symposium on the Foundations of Computer Science (1978), pp. 113–122.

  12. Paul, W. and Reischuk, R., On alternation II,Acta Informatica, 14 (1980), pp. 391–403.

    Google Scholar 

  13. Pippenger, N., On simultaneous resource bounds,Proc. 20th Annual Symposium on the Foundations of Computer Science, Oct., 1979, pp. 307–311.

  14. Pippenger, N., Pebbling, inProc. of the 5th IBM Symposium on Foundations of Computer Science, IBM Japan (1980).

  15. Ruby, S. and Fischer, P. C., Translational methods in computational complexity, IEEE Conference record on switching circuit theory and Logical Design, Sixth Annual Symposium (1965), pp. 173–178.

  16. Seiferas, J. I., Fischer, M. J., and Meyer, A. R., Separating nondeterministic time complexity classes,JACM, 25, 1, Jan. (1978), pp. 146–167.

    Google Scholar 

Download references

Author information

Author notes

  1. Ravindran Kannan

    Present address: Dept. of Computer Science, Carnegie-Mellon University, Schenley Park, 15213, Pittsburgh, PA, USA

Authors and Affiliations

  1. Mathematics Department, Massachusetts Institute of Technology, 02139, Cambridge, Massachusetts, USA

    Ravindran Kannan

Authors
  1. Ravindran Kannan
    View author publications

    You can also search for this author inPubMed Google Scholar

Additional information

Supported by NSF Grant No. MCS-8105557

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kannan, R. Towards separating nondeterminism from determinism. Math. Systems Theory 17, 29–45 (1984). https://doi.org/10.1007/BF01744432

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01744432

Keywords