| 000 | nam a22 7i 4500 | ||
|---|---|---|---|
| 999 |
_c34873 _d34873 |
||
| 005 | 20181017062628.0 | ||
| 008 | 140202s2009 e ad||f |||| 00| 0 eng d | ||
| 020 | _a9780521424264 | ||
| 040 |
_aCO-NeUS _beng _erda |
||
| 100 | 1 |
_aArora, Sanjeev _928562 _eaut |
|
| 245 | 1 | 0 |
_aComputational Complexity : _bA Modern Approach / _cSanjeev Arora, Boaz Barak |
| 250 | _aFirst edition | ||
| 264 |
_aCambridge : _aNew York : _bCambridge University Prees, _c2009 |
||
| 300 |
_axxiv, 579 pages : _billustrated ; _c25 cm. |
||
| 336 |
_2rdacontent _atxt _btxt |
||
| 337 |
_2rdamedia _an |
||
| 338 |
_2rdacarrier _anc |
||
| 504 | _aIncludes bibliographical references (p. 549-573) and indexes. | ||
| 505 | 0 | 0 | _aNotational conventions -- Basic Complexity Classes -- The computational model-and why it dosen´t matter -- NP and NP completeness -- Diagonalization -- Space complexity -- The polynomial hierarchy and alternations -- Boolean circuits -- Randomized computation -- Interactive proofs -- Crytography -- Quantum computation -- PCP theorem and hardness of approximation : An introduction -- Lower Bounds for Concrete Computational Models -- Communication complexity -- Circuit lower brounds : Complexity theory´s Waterloo -- Proof complexity -- Advanced topics -- Complexity of counting -- Average case complexity : Levin´s theory -- Hardness amplification and error-correcting codes -- Pseudorandom constructions : Expander and extractors -- Why are circuit lower bounds so difficult? -- Appendix : Mathematical background -- Bibliography -- |
| 700 | 1 |
_aBarak, Boaz _929574 _eaut |
|
| 082 | 0 | 4 |
_221 _a511.352 / _bA769c |
| 650 | 1 | 4 |
_aComputational complexity _9103999 |
| 650 | 1 | 4 |
_aComplejidad computacional _9103816 |
| 650 | 1 | 4 |
_aCriptografía _9105184 |
| 650 | 1 | 4 |
_aLógica matemática (simbólica) _9115237 |
| 650 | 1 | 2 |
_aComputadores cuánticos _9137965 _2[MeSH] |
| 942 |
_2ddc _cCG |
||