Tools

LEADER 02985cam a22005054a 4500

001 ocn642204747;

003 OCoLC;

005 20141212054331.0;

008 100608s2010 nyua b 001 0 eng ;

010 a| 2010023587;

020 a| 9780521192484 (hardback);

020 a| 052119248X (hardback);

020 a| 9780521122542 (pbk.);

020 a| 0521122546 (pbk.);

029 1 a| AU@b| 000045747506;

029 1 a| HEBISb| 228769841;

035 a| (Sirsi) o642204747;

035 a| (OCoLC)642204747;

042 a| pcc;

049 a| EREE;

050 00 a| QA267.7b| .G652 2010;

082 00 a| 005.12| 22;

100 1 a| Goldreich, Oded.=| ^A489217;

245 10 a| P, NP, and NP-completeness :b| the basics of computational complexity /c| Oded Goldreich.;

260 a| New York :b| Cambridge University Press,c| 2010.;

300 a| xxix, 184 pages :b| illustrations ;c| 24 cm;

336 a| text2| rdacontent;

337 a| unmediated2| rdamedia;

338 a| volume2| rdacarrier;

504 a| Includes bibliographical references and index.;

505 8 a| Machine generated contents note: 1. Computational tasks and models; 2. The P versus NP Question; 3. Polynomial-time reductions; 4. NP-completeness; 5. Three relatively advanced topics; Epilogue: a brief overview of complexity theory.;

520 a| "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"--Provided by publisher.;

650 0 a| Computational complexity.=| ^A74807;

650 0 a| Computer algorithms.=| ^A285321;

650 0 a| Approximation theory.=| ^A16000;

650 0 a| Polynomials.=| ^A25840;

856 42 3| Cover imageu| http://assets.cambridge.org/97805211/92484/cover/9780521192484.jpg;

949 a| QA267.7b| .G652 2010h| JOYNER48o| jmpli| 30372014919291;

994 a| C0b| ERE;

938 a| Coutts Information Servicesb| COUTn| 11521580;

938 a| YBP Library Servicesb| YANKn| 3470335;

596 a| 1;

998 a| 2379434;

999 a| QA267.7 .G652 2010w| LCc| 1i| 30372014919291d| 4/2/2013e| 1/16/2013f| 2/13/2012g| 2l| JGESm| JOYNERn| 5r| Ys| Yt| JGESBKu| 1/18/2011x| BOOKz| JSTACKSo| .STAFF. jmpl;

P, NP, and NP-completeness : the basics of computational complexity / Oded Goldreich.

Author/creator	Goldreich, Oded
Format	Book
Publication Info	New York : Cambridge University Press, 2010.
Description	xxix, 184 pages : illustrations ; 24 cm
Supplemental Content	Cover image
Subjects	Computational complexity. Computer algorithms. Approximation theory. Polynomials.

Contents	Machine generated contents note: 1. Computational tasks and models; 2. The P versus NP Question; 3. Polynomial-time reductions; 4. NP-completeness; 5. Three relatively advanced topics; Epilogue: a brief overview of complexity theory.
Abstract	"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"--Provided by publisher.
Bibliography note	Includes bibliographical references and index.
LCCN	2010023587
ISBN	9780521192484 (hardback)
ISBN	052119248X (hardback)
ISBN	9780521122542 (pbk.)
ISBN	0521122546 (pbk.)

Availability

Library	Location	Call Number	Status	Item Actions
Joyner	General Stacks	QA267.7 .G652 2010	✔ Available	Place Hold

P, NP, and NP-completeness : the basics of computational complexity / Oded Goldreich.

Click here for more information about this title

Availability