000			01568nam a2200217 a 4500
003			AR-LpUFIB
005			20250311170358.0
008			230201s2009 xxu r 000 0 ||| d
020			_a9780521424264
024	8		_aDIF-M5711 _b5815 _zDIF005335
040			_aAR-LpUFIB _bspa _cAR-LpUFIB
100	1		_aArora, Sanjeev
245	1	0	_aComputational complexity : _bA modern approach
260			_aNueva York : _b Cambridge University Press, _c2009
300			_axxiv, 579 p.
505	0		_a 0. Notational conventions -- 1. The computacional model- and why it doesn’t matter. -- 2. NP and NP complétense. -- 3. Diagonalization. -- 4. Space complexity. -- 5. The polinomial hierarchy and alternations. -- 6. Boolean circuits. -- 7. Randomized computation. -- 8. Interactive Prof.. -- 9. Cryptography. -- 10. Quantum computation. -- 11. PCP theorem and hardness of approximation: An introduction. -- 12. Decision trees. -- 13. Comunication complexity. -- 14. Circuit lower bpunds: Complexity theory’s Waterloo. -- 15. Proof complexity. -- 16. Algebraic computation models. -- 17. Complexity of counting. -- 18. Average case complexity: Levin’s theory. -- 19. Hardness amplification and error-correcting codes. -- 20. Derandomization. -- 21. Pseudorandom constructions: Expander and extractors. -- 22. Proof of PCP theorems and the Fourier transform technique. -- 23. Why are circuit lower bounds so difficult? -- Appendix: Mathematical background.
650		4	_aCOMPLEJIDAD COMPUTACIONAL
650		4	_aMODELOS COMPUTACIONALES
700	1		_aBarak, Boaz
942			_cBK
999			_c55124 _d55124