{"id":256687,"date":"2026-07-13T14:59:41","date_gmt":"2026-07-13T11:59:41","guid":{"rendered":"https:\/\/1kitap1.com\/en\/computational-complexity-sanjeev-arora\/"},"modified":"2026-07-13T14:59:41","modified_gmt":"2026-07-13T11:59:41","slug":"computational-complexity-sanjeev-arora","status":"publish","type":"post","link":"https:\/\/1kitap1.com\/en\/computational-complexity-sanjeev-arora\/","title":{"rendered":"Computational Complexity – Sanjeev Arora"},"content":{"rendered":"
\"<\/figure>\n

Two views of the PCP Theorem. Proof view Hardness of approximation view PCP veri\ufb01er (V) \u2190\u2192 CSP instance (\u03d5) PCP proof (\u03c0) \u2190\u2192 Assignment to variables (u) Length of proof \u2190\u2192 Number of variables (n) Number of queries (q) \u2190\u2192 Arity of constraints (q) Number of random bits (r) \u2190\u2192 Logarithm of number of constraints (log m) Soundness parameter (typically 1\/2) \u2190\u2192 Maximum of val(\u03d5) for a NO instance Theorem 11.5 (NP \u2286PCP(log n, 1)) \u2190\u2192 Theorem 11.14 (\u03c1-GAPqCSP is NP-hard) , Theorem 11.9 (MAX-3SAT is NP-hard to \u03c1-approximate) while if x\u0338 \u2208L, it will accept with probability at most \u03c1.<\/p>\n

The soundness can be boosted to 1\/2 at the expense of a constant factor in the randomness and number of queries (see Exercise 11.1). \u25a0 Theorem 11.9 is equivalent to Theorem 11.14 Since 3CNF formulas are a special case of 3CSP instances, Theorem 11.9 implies Theorem 11.14. We now show the other direction.<\/p>\n

Let \u03f5 > 0 and q \u2208N be such that by Theorem 11.14, (1 \u2212\u03f5)-GAPqCSP is NP-hard. Let \u03d5 be a qCSP instance over n variables with m constraints. Each constraint \u03d5i of \u03d5 can be expressed as an AND of at most 2q clauses, where each clause is the OR of at most q variables or their negations. Let \u03d5\u2032 denote the collection of at most m2q clauses corresponding to all the constraints of \u03d5. If \u03d5 is a YES instance of (1\u2212\u03f5)-GAPqCSP (i.e., it is satis\ufb01able), then there exists an assignment satisfying all the clauses of \u03d5\u2032.<\/p>\n

If \u03d5 is a NO instance of (1\u2212\u03f5)-GAPqCSP, then every assignment violates at least an \u03f5 fraction of the constraints of \u03d5 and hence violates at least an \u03f5 2q fraction of the constraints of \u03d5\u2032. We can use the Cook-Levin technique of Chapter 2 (Theorem 2.10), to transform any clause C on q variables u1, . . . , uq to a set C1, . . .<\/p>\n

\n

This 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.<\/p>\n

More than 300 exercises are included with a selected hint set. The book starts with a broad introduction to the \ufb01eld and progresses to advanced results. Contents include de\ufb01nition of Turing machines and basic time and space complexity classes, probabilistic algorithms, inter- active proofs, cryptography, quantum computation, lower bounds for concrete computational models (decision trees, communication complex- ity, constant depth, algebraic and monotone circuits, proof complexity), average-casecomplexityandhardnessampli\ufb01cation, derandomizationand pseudorandom constructions, and the PCP Theorem.<\/p>\n

Sanjeev Arora is a professor in the department of computer science at Princeton University. He has done foundational work on probabilistically checkable proofs and approximability of NP-hard problems. He is the founding director of the Center for Computational Intractability, which is funded by the National Science Foundation. Boaz Barak is an assistant professor in the department of computer science at Princeton University. He has done foundational work in computational complexity and cryptography, especially in developing \u201cnon-blackbox\u201d techniques. COMPUTATIONAL COMPLEXITY A Modern Approach SANJEEV ARORA Princeton University BOAZ BARAK Princeton University CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, S\u00e3o Paulo Cambridge University Press The Edinburgh Building, Cambridge CB2 8RU, UK First published in print format ISBN-13 978-0-521-42426-4 ISBN-13 978-0-511-53381-5 \u00a9 Sanjeev Arora and Boaz Barak 2009 2007 Information on this title: www.cambridge.org\/9780521424264 This publication is in copyright.<\/p>\n

Subject to statutory exception and to the provision of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. Cambridge University Press has no responsibility for the persistence or accuracy of urls for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate.<\/p>\n

Published in the United States of America by Cambridge University Press, New York www.cambridge.org eBook (EBL) hardback To our wives\u2014Silvia and Ravit Contents About this book page xiii Acknowledgments xvii Introduction xix 0 Notational conventions . . . . . . . . . .<\/p>\n

. . . . . . . . . . . . . . . . . 1 0.1 Representing objects as strings 2 0.2 Decision problems\/languages 3 0.3 Big-oh notation 3 exercises 4 PART ONE: BASIC COMPLEXITY CLASSES 7 1 The computational model\u2014and why it doesn\u2019t matter . . . . . .<\/p>\n

. . . .<\/p>\n<\/blockquote>\n

This is a short excerpt from the opening of “” by Unknown, quoted for review and introduction purposes. All rights belong to the copyright holders.<\/em><\/p>\n

\n
\n

Table of Contents<\/p>\nToggle<\/span><\/path><\/svg><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n