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,” 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 [?] 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, 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 ["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), 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 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" vel "Curve fitting") 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.)