Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

Book Review

The AMS does not provide abstracts of book reviews. You may download the entire review from the links below.


Full text of review: PDF   This review is available free of charge.
Book Information:

Authors: Michael R. Garey and David S. Johnson
Title: Computers and intractability: A guide to the theory of $NP$-completeness
Additional book information: W. H. Freeman and Company, San Francisco, 1979, xii + 338 pp., $10.00 (paper).

References [Enhancements On Off] (What's this?)

  • 1. A Cobham, The intrinsic computational difficulty of functions, Y. Bar-Hillel (ed.), (Proc. 1964 Internat. Congr.), Logic, Methodology and Philos. Sci., North-Holland, Amsterdam, 1965, pp. 24-30. MR 207561
  • 2. J. Edmunds, Paths, trees and flowers, Canad. J. Math. 17 (1965), 449-467. MR 177907
  • 3. S. Cook, The complexity of theorem-proving procedures, Proc. 3rd ACM Sympos. on Theory of Computing, J. Assoc. Comput. Mach. (1971), 151-158.
  • 4. A. Goldberg, On the complexity of the satisfiability problem, Ph.D. dissertation, Courant Institute of Mathematical Sciences, 1979.
  • 5. R. Karp, Reducibility among combinatorial problems, R. Miller and J. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, New York, 1972, pp. 85-103. MR 378476

Review Information:

Reviewer: Ronald V. Book
Journal: Bull. Amer. Math. Soc. 3 (1980), 898-904
DOI: https://doi.org/10.1090/S0273-0979-1980-14848-X
American Mathematical Society