Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
Mobile Device Pairing
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

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 (34 #7376)
  • 2. Jack Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965), 449–467. MR 0177907 (31 #2165)
  • 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 (51 #14644)

Review Information

Reviewer: Ronald V. Book
Journal: Bull. Amer. Math. Soc. 3 (1980), 898-904
PII: S 0273-0979(1980)14848-X