Computers and intractability: A guide to the theory of NP-completeness (A Series of books in the mathematical sciences)

Chapters 1 & 2 are an excellent intro to P, NP, NP-complete, and (non)deterministic Turing machines ((N)DTMs). cited in: * Tad Hogg, “[Adiabatic Quantum Computing for Random Satisfiability Problems](https://isidore.co/misc/Physics%20papers%20and%20books/Zotero/storage/QEVVSZJ4/Hogg%20-%202003%20-%20Adiabatic%20quantum%20computing%20for%20random%20satisfiabil.pdf),” *Physical Review A* 67, no. 2 (February 28, 2003): 022314. * * * "Although this may seem a paradox, all exact science is dominated by the idea of approximation." —Bertrand Russell (1872-1970) Most natural optimization problems, including those arising in important application areas, are NP-hard. Therefore, under the [widely believed [?]](https://isidore.co/misc/Physics%20papers%20and%20books/Zotero/storage/B8FHLCMA/Gasarch%20-%202012%20-%20Guest%20Column%20the%20second%20P%20%E2%89%9F%20NP%20poll.pdf) conjecture that P ≠ NP, their exact solution is prohibitively time consuming. Charting the landscape of approximability of these problems, via polynomial time algorithms, therefore becomes a compelling subject of scientific inquiry in computer science and mathematics. This book presents the theory of ap proximation algorithms as it stands today. It is reasonable to expect the picture to change with time. This book is divided into three parts. In Part I we cover combinatorial algorithms for a number of important problems, using a wide variety of algorithm design techniques. The latter may give Part I a non-cohesive appearance. However, this is to be expected — nature is very rich, and we cannot expect a few tricks to help solve the diverse collection of NP-hard problems. Indeed, in this part, we have purposely refrained from tightly categorizing algorithmic techniques so as not to trivialize matters. Instead, we have attempted to capture, as accurately as possible, the individual character of each problem, and point out connections between problems and algorithms for solving them. * * * [**NP**](https://www.oed.com/view/Entry/246265), *n*. The class of problems for which an algorithm exists for checking the correctness of solutions (reached by guessing or trial and error) in a length of time or number of steps which is a polynomial function of the size of the input. Frequently *attributive* or as *adj.* : designating such a problem, esp. one for which an algorithm producing a general solution in polynomial time is not known. In computational theory, NP represents the class of formal languages that can be recognized by a [nondeterministic](https://www.oed.com/view/Entry/246073) ["Of, relating to, or designating a mode of computation in which, at certain points, there is an unpredictable choice of ways to proceed."] Turing machine in polynomial time. Interest is focused on the subdivision of this class containing the complex and intractable problems termed NP-complete (see [Compounds](https://www.oed.com/view/Entry/246265#eid12214987)), including the travelling salesman problem and the factorization of large integers, and on the conjecture that all NP problems could have polynomial-time algorithms (widely believed to be false, or perhaps indeterminable). 1989 R. Penrose [*Emperor's New Mind*](https://isidore.co/calibre/#panel=book_details&book_id=8928) 144 Problems in **NP** which are not in **P** are regarded as being ‘intractable’ (i.e. though soluble in principle, they are ‘insoluble in practice’) for reasonably large *n*. **N** **P-complete** *adj*. designating a member of a class of complex and intractable NP problems which can be converted into any other problem of the same class, such that if an algorithm for its solution in polynomial time existed, it would be possible to solve all NP problems in polynomial time; (of a problem) both NP and NP-hard. **N** **P-hard** *adj*. designating an intractable problem (whether or not NP) which may be polynomially reduced to an NP-complete problem. * * * P≟NP should be discussed more, with all the "AI" (= "[Another name for probability models](https://www.wmbriggs.com/post/6465/)" *vel* "[Curve fitting](https://www.wmbriggs.com/post/27654/)") hype floating around. Its resolution would seem to have a profound impact on the philosophy of knowledge. Some thoughts/musings I can muster * in favor of P = NP: * The real distinction is between ratiocinative (human (≟algorithmic)) and non-ratiocinative (angelic (≟non-algorithmic)) reasoning; thus, all algorithmic reasoning, whether involving deterministic or nondeterministic parts, is the fundamentally the same. * Nondeterministic Turing machines aren't possible, just as pseudorandom number generators are not truly random. * Monte Carlo algorithms always have non-Monte Carlo analogues. * in favor of P ≠ NP: * Something nondeterministic (random, *in potentia* ) cannot determine something deterministic ( *in re* )—i.e., potentiality cannot actualize itself. * though NP algorithms do have a polynomial runtime deterministic "checking" part, so they're not pure potentiality * Some truths are indemonstrable ( *dicit* Aristotle, Gödel); these are in NP. (And all demonstrable truths are in P.) "Shows how to recognize NP-complete problems and offers proactical suggestions for dealing with them effectively. The book covers the basic theory of NP-completeness, provides an overview of alternative directions for further research, and contains and extensive list of NP-complete and NP-hard problems, with more than 300 main entries and several times as many results in total. [This book] is suitable as a supplement to courses in algorithm design, computational complexity, operations research, or combinatorial mathematics, and as a text for seminars on approximation algorithms or computational complexity. It provides not only a valuable source of information for students but also an essential reference work for professionals in computer science"--Back cover In computer science, more specifically computational complexity theory, Computers and Intractability: A Guide to the Theory of NP-Completeness is an influential textbook by Michael Garey and David S. Johnson. It was the first book exclusively on the theory of NP-completeness and computational intractability. The book features an appendix providing a thorough compendium of NP-complete problems (which was updated in later printings of the book). The book is now outdated in some respects as it does not cover more recent development such as the PCP theorem. It is nevertheless still in print and is regarded as a classic: in a 2006 study, the CiteSeer search engine listed the book as the most cited reference in computer science literature. Contents Preface Computers, Complexity, and Intractability The Theory of NP-Completeness Proving NP-Completeness Results Using NP-Completeness to Analyze Problems NP-Hardness Coping with NP-Complete Problems Beyond NP-Completeness A List of NP-Complete Problems Symbol Index Reference and Author Index Subject Index Update for the Current Printing Michael R. Garey, David S. Johnson. Includes Indexes. Includes Update For The Second Printing. Bibliography: P. [291]-325.