没有合适的资源?快使用搜索试试~ 我知道了~
Computational Complexity - A Modern Approach
5星 · 超过95%的资源 需积分: 15 35 下载量 118 浏览量
2011-07-16
12:29:17
上传
评论
收藏 3.02MB PDF 举报
温馨提示
试读
603页
Computational Complexity - A Modern Approach, Sanjeev Arora _ 正式版 _ 软件所参考书之一
资源推荐
资源详情
资源评论
COMPUTATIONAL COMPLEXITY
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. 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, 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-casecomplexityandhardnessamplification, derandomizationand
pseudorandom constructions, and the PCP Theorem.
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 “non-blackbox”
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ão 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
© Sanjeev Arora and Boaz Barak 2009
2007
Information on this title: www.cambrid
g
e.or
g
/9780521424264
This publication is in copyright. 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.
Published in the United States of America by Cambridge University Press, New York
www.cambridge.org
eBook
(
EBL
)
hardback
To our wives—Silvia and Ravit
剩余602页未读,继续阅读
资源评论
- JerM_thunk2012-05-18介绍计算复杂性理论的经典著作
alansoft
- 粉丝: 0
- 资源: 6
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功