000			01584nam a22002177a 4500
005			20250801111555.0
006			a|||||r|||||||||||
008			s1994 a b 001 0 eng d
020			_a0201530821
040			_aGR-AtMCL _dGR-AtMCL _bgre _eAACR2
100	1		_aPapadimitriou, Christos H. _94748
245	1	0	_aComputational complexity / _cChristos H. Papadimitriou.
260			_aReading, Mass. : _bAddison-Wesley, _cc1994.
300			_axv, 523 p. : _bill. ; _c25 cm.
504			_aIncludes bibliographical references and indexes.
520			_aThis text offers a comprehensive and accessible treatment of the theory of algorithms and complexity - the elegant body of concepts and methods developed by computer scientists over the past 30 years for studying the performance and limitations of computer algorithms. Among topics covered are: reductions and NP-completeness, cryptography and protocols, randomized algorithms, and approximability of optimization problems, circuit complexity, the "structural" aspects of the P=NP question, parallel computation, the polynomial hierarchy, and many others. Several sophisticated and recent results are presented in a rather simple way, while many more are developed in the form of extensive notes, problems, and hints. The book is surprisingly self-contained, in that it develops all necessary mathematical prerequisites from such diverse fields as computability, logic, number theory, combinatorics and probability.
650		0	_aComputational complexity _99901
650		0	_aComputing _99851
942			_cBK
999			_c9845 _d9845