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