000			01817nam a22002057a 4500
005			20240625143635.0
008			240625b |||||||| |||| 00| 0 eng d
020			_a9781316612156 (PB)
041			_geng
082			_a511.352 _bARO
100			_aArora,Sanjeev
245			_aComputational Complexity: _bA Modern Approach
260			_aNew Delhi _bCambridge University Press _c2021
300			_axxiv,579 P
505			_t0 Notational conventions PART ONE BASIC COMPLEXITY CLASSES PART TWO LOWER BOUNDS FOR CONCRETE COMPUTATIONAL MODELS PART THREE ADVANCED TOPICS Appendix: Mathematical background Hints and selected exercises Main theorems and definitions Bibliography Index Complexity class
520			_aThis beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. More than 300 exercises are included with a selected hint set. The book starts with a broad introduction to the field and progresses to advanced results. Contents include: definition of Turing machines and basic time and space complexity classes, probabilistic algorithms, interactive proofs, cryptography, quantum computation, lower bounds for concrete computational models (decision trees, communication complexity, constant depth, algebraic and monotone circuits, proof complexity), average-case complexity and hardness amplification, derandomization and pseudorandom constructions, and the PCP theorem.
650			_aComputational complexity
700			_aBarak,Boaz
942			_2ddc _cBK
999			_c2279 _d2279