000			01862nam a2200289 a 4500
999			_c22116 _d22116
001			BD-DhNSU-22116
003			BD-DhNSU
005			20211018112355.0
008			211018s2010 nyua|||g |||| 001 0|eng d
020			_a9780521122542
040			_aDLC _cBD-DhNSU _dBD-DhNSU
041			_aeng
050	0	0	_aQA267.7 _b.G65 2010
100	1		_aGoldreich, Oded _923474
245	0	0	_aP, NP, and NP-completeness : _bthe basics of computational complexity / _cOded Goldreich
260			_aNew York : _bCambridge University Press, _cc2010.
300			_axxix, 184 p. : _bill. ; _c22+ cm.
504			_aIncludes bibliographical references and index.
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"
526	0		_aComputer Science & Engineering
590			_aDilruba Rahman
650		0	_aComputational complexity _91510
650		4	_aComputer algorithms _923475
650		4	_aApproximation theory _923476
650		4	_a Polynomials. _923477
942			_2lcc _cBK