|
|
|
|
| LEADER |
00000nam a2200000 a 4500 |
| 003 |
AR-LpUFIB |
| 005 |
20250311170358.0 |
| 008 |
230201s2009 xxu r 000 0 ||| d |
| 020 |
|
|
|a 9780521424264
|
| 024 |
8 |
|
|a DIF-M5711
|b 5815
|z DIF005335
|
| 040 |
|
|
|a AR-LpUFIB
|b spa
|c AR-LpUFIB
|
| 100 |
1 |
|
|a Arora, Sanjeev
|
| 245 |
1 |
0 |
|a Computational complexity :
|b A modern approach
|
| 260 |
|
|
|a Nueva York :
|b Cambridge University Press,
|c 2009
|
| 300 |
|
|
|a xxiv, 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 |
|a COMPLEJIDAD COMPUTACIONAL
|
| 650 |
|
4 |
|a MODELOS COMPUTACIONALES
|
| 700 |
1 |
|
|a Barak, Boaz
|
| 942 |
|
|
|c BK
|
| 952 |
|
|
|0 0
|1 0
|4 0
|6 F2_ARO
|7 0
|9 79997
|a DIF
|b DIF
|d 2025-03-11
|i DIF-03794
|l 3
|m 1
|o F.2 ARO
|p DIF-03794
|q 2025-04-16
|r 2025-03-13 15:33:55
|s 2025-03-13
|w 2025-03-11
|y BK
|
| 999 |
|
|
|c 55124
|d 55124
|
