000			01241nam a2200217 a 4500
003			AR-LpUFIB
005			20250311170409.0
008			230201s2008 xxua r 000 0 eng d
020			_a9780521884730
024	8		_aDIF-M6185 _b6312 _zDIF005674
040			_aAR-LpUFIB _bspa _cAR-LpUFIB
100	1		_aGoldreich, Oded
245	1	0	_aComputational complexity : _ba conceptual perspective
250			_a1st ed.
260			_aCambridge : _b Cambridge University Press, _c2008
300			_axxiv, 606 p. : _bil.
500			_aIncluye índice y bibliografía.
505	0		_a 1. Introduction and preliminaries -- 2. P, NP and NP-completeness -- 3. Variations on P and NP -- 4. More resources, more power? -- 5. Space complexity -- 6. Randomness and counting -- 7. The bright side of hardness -- 8. Pseudorandom generators -- 9. Probabiistic proof systems -- 10. Relaxing the requirements -- Epilogue -- A. Glossary of complexity classes -- B. On the quest for lower bounds -- C. On the foundations of modern cryptography -- D. Probabilistic preliminaries and advanced topics in randomization -- E. Explicit constructions -- F. Some omitted proofs -- G. Some computational problems.
650		4	_aCOMPLEJIDAD COMPUTACIONAL
942			_cBK
999			_c55461 _d55461