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. Alan Cobham, The intrinsic computational difficulty of functions, Logic, Methodology and Philos. Sci. (Proc. 1964 Internat. Congr.), North-Holland, Amsterdam, 1965, pp. 24–30. MR 0207561
  • 2. Jack Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965), 449–467. MR 0177907,
  • 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. Richard M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) Plenum, New York, 1972, pp. 85–103. MR 0378476

Review Information:

Reviewer: Ronald V. Book
Journal: Bull. Amer. Math. Soc. 3 (1980), 898-904