P, NP, and NP-completeness : the basics of computational complexity /
Goldreich, Oded.
P, NP, and NP-completeness : the basics of computational complexity / Oded Goldreich. - Cambridge ; New York : Cambridge University Press, ©2010. - 1 online resource (xxix, 184 pages) : illustrations
Includes bibliographical references (pages 181-182) and index.
Computational tasks and models -- The P versus NP question -- Polynomial-time reductions -- NP-completeness -- Three relatively advanced topics -- Epilogue: a brief overview of complexity theory.
"The focus of this book is the P-versus-NP Question and the theory of NP-completeness. It also provides adequate preliminaries regarding computational problems and computational models. The P-versus-NP Question asks whether or not finding solutions is harder than checking the correctness of solutions. An alternative formulation asks whether or not discovering proofs is harder than verifying their correctness. It is widely believed that the answer to these equivalent formulations is positive, and this is captured by saying that P is different from NP. Although the P-versus-NP Question remains unresolved, the theory of NP-completeness offers evidence for the intractability of specific problems in NP by showing that they are universal for the entire class. Amazingly enough, NP-complete problems exist, and furthermore hundreds of natural computational problems arising in many different areas of mathematics and science are NP-complete"--
English.
9780511909443 (electronic bk.) 0511909446 (electronic bk.) 9780511906657 (ebook) 051190665X (ebook) 1282797662 9781282797666 (hardback) (hardback) (pbk.) (pbk.) 9780511761355 (ebook) 051176135X 1139929771 9781139929776 9786612797668 6612797665 0511908687 9780511908682 0511905378 9780511905377 0511907931 9780511907937
9786612797668
279766 MIL
Computational complexity.
Computer algorithms.
Approximation theory.
Polynomials.
Algorithms
Complexité de calcul (Informatique)
Algorithmes.
Théorie de l'approximation.
Polynômes.
algorithms.
COMPUTERS--Programming--Open Source.
COMPUTERS--Software Development & Engineering--Tools.
COMPUTERS--Software Development & Engineering--General.
Approximation theory.
Computational complexity.
Computer algorithms.
Polynomials.
Electronic books.
Electronic books.
QA267.7 / .G652 2010eb
005.1
P, NP, and NP-completeness : the basics of computational complexity / Oded Goldreich. - Cambridge ; New York : Cambridge University Press, ©2010. - 1 online resource (xxix, 184 pages) : illustrations
Includes bibliographical references (pages 181-182) and index.
Computational tasks and models -- The P versus NP question -- Polynomial-time reductions -- NP-completeness -- Three relatively advanced topics -- Epilogue: a brief overview of complexity theory.
"The focus of this book is the P-versus-NP Question and the theory of NP-completeness. It also provides adequate preliminaries regarding computational problems and computational models. The P-versus-NP Question asks whether or not finding solutions is harder than checking the correctness of solutions. An alternative formulation asks whether or not discovering proofs is harder than verifying their correctness. It is widely believed that the answer to these equivalent formulations is positive, and this is captured by saying that P is different from NP. Although the P-versus-NP Question remains unresolved, the theory of NP-completeness offers evidence for the intractability of specific problems in NP by showing that they are universal for the entire class. Amazingly enough, NP-complete problems exist, and furthermore hundreds of natural computational problems arising in many different areas of mathematics and science are NP-complete"--
English.
9780511909443 (electronic bk.) 0511909446 (electronic bk.) 9780511906657 (ebook) 051190665X (ebook) 1282797662 9781282797666 (hardback) (hardback) (pbk.) (pbk.) 9780511761355 (ebook) 051176135X 1139929771 9781139929776 9786612797668 6612797665 0511908687 9780511908682 0511905378 9780511905377 0511907931 9780511907937
9786612797668
279766 MIL
Computational complexity.
Computer algorithms.
Approximation theory.
Polynomials.
Algorithms
Complexité de calcul (Informatique)
Algorithmes.
Théorie de l'approximation.
Polynômes.
algorithms.
COMPUTERS--Programming--Open Source.
COMPUTERS--Software Development & Engineering--Tools.
COMPUTERS--Software Development & Engineering--General.
Approximation theory.
Computational complexity.
Computer algorithms.
Polynomials.
Electronic books.
Electronic books.
QA267.7 / .G652 2010eb
005.1