000			02735nam a22003378i 4500
001			CR9780511804106
003			UkCbUP
005			20200124160250.0
006			m|||||o||d||||||||
007			cr||||||||||||
008			101021s2008||||enk o ||1 0|eng|d
020			_a9780511804106 (ebook)
020			_z9780521884730 (hardback)
040			_aUkCbUP _beng _erda _cUkCbUP
050	0	0	_aQA267.7 _b.G65 2008
082	0	0	_a511.3/52 _222
100	1		_aGoldreich, Oded, _eauthor.
245	1	0	_aComputational complexity : _ba conceptual perspective / _cOded Goldreich.
264		1	_aCambridge : _bCambridge University Press, _c2008.
300			_a1 online resource (xxiv, 606 pages) : _bdigital, PDF file(s).
336			_atext _btxt _2rdacontent
337			_acomputer _bc _2rdamedia
338			_aonline resource _bcr _2rdacarrier
500			_aTitle from publisher's bibliographic system (viewed on 05 Oct 2015).
505	0		_aIntroduction and preliminaries -- P, NP and NP-completeness -- Variations on P and NP -- More resources, more power -- Space complexity -- Randomness and counting -- The bright side of hardness -- Pseudorandom generators -- Probabilistic proof systems -- Relaxing the requirements -- Appendix A: Glossary of complexity classes -- Appendix B: On the quest for lower bounds -- Appendix C: On the foundations of modern cryptography -- Appendix D: Probabilistic preliminaries and advanced topics in randomization -- Appendix E: Explicit constructions -- Appendix F: Some omitted proofs -- Appendix G: Some computational problems.
520			_aComplexity theory is a central field of the theoretical foundations of computer science. It is concerned with the general study of the intrinsic complexity of computational tasks; that is, it addresses the question of what can be achieved within limited time (and/or with other limited natural computational resources). This book offers a conceptual perspective on complexity theory. It is intended to serve as an introduction for advanced undergraduate and graduate students, either as a textbook or for self-study. The book will also be useful to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems. In each case, the author starts by posing the intuitive questions that are addressed by the sub-area and then discusses the choices made in the actual formulation of these questions, the approaches that lead to the answers, and the ideas that are embedded in these answers.
650		0	_aComputational complexity.
650		0	_aTuring machines.
776	0	8	_iPrint version: _z9780521884730
856	4	0	_uhttps://doi.org/10.1017/CBO9780511804106
999			_c519380 _d519378