About the Book
Please note that the content of this book primarily consists of articles available from Wikipedia or other free sources online. Pages: 44. Chapters: NP-hard, PSPACE-complete, Co-NP, EXPTIME, P-complete, NC, Sharp-P-complete, Co-NP-complete, EXPSPACE, NP-easy, NP-equivalent, Complexity class, Arithmetical hierarchy, FO, SL, NL, List of complexity classes, ACC0, P/poly, ELEMENTARY, PPAD, DTIME, Polynomial-time approximation scheme, Strongly NP-complete, NEXPTIME, DSPACE, Pseudo-polynomial time, APX, RE, SNP, Parity P, NP-Intermediate, FP, 2-EXPTIME, FNP, TC, PPP, UP, PH, Weakly NP-complete, TC0, NSPACE, NL-complete, PolyL, FL, AC0, TFNP, NTIME, Exponential hierarchy, PLS, LOGCFL, Random-access Turing machine, LH, GapP, DLOGTIME, L/poly, NONELEMENTARY, ALL, ESPACE, QP. Excerpt: In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC) is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard problems so that any NP problem can be converted into L by a transformation of the inputs in polynomial time. Although any given solution to such a problem can be verified quickly, there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a result, the time required to solve even moderately large versions of many of these problems easily reaches into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether or not it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer scienc...
