Arora, Sanjeev <br/><br/>
Computational complexity :  A modern approach 

 - Nueva York :  ,  2009 
<br/><br/>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. 
<br/><br/><label>ISBN: </label>9780521424264 
<br/><br/><label>Standard No.: </label>DIF005324 
<br/><br/><label>Subjects--Topical Terms: </label><br/>COMPLEJIDAD COMPUTACIONAL<br/>MODELOS COMPUTACIONALES