Trending on TikTok

Buldak

Sunscreen

Sanrio

English

{{sellerTotalView > 1 ? __("sellers", {number: sellerTotalView}) : __("seller", {number: sellerTotalView}) }}, {{numTotalView > 1 ? __("items", {number: numTotalView}) : __("item", {number: numTotalView}) }}

View Cart & Check Out

Nickname

Let us know how to properly address you.

Update Your Name

xxxxxxx@yamibuy.com

Account Orders Favorites

Points 0

Coupons 0

Gift Card Balance $0.00

Sign Out

Change Your Zip Code

Inventory information and delivery speeds may vary for different locations.

Location History

We will notify you by email when the item back in stock.

Your email: {{remindEmail}}

Cancel

Jingdong book

计算复杂性

View Cart & Check Out

{{buttonTypePin == 3 ? __("Scan to view more PinGo") : __("Scan to start")}}

Books Computers & Internet Computer Theory

Jingdong book

计算复杂性

Name: 计算复杂性
Brand: Jingdong book
SKU: 3118001221
Price: 60.76 USD
Availability: OutOfStock

{{__(":people-members", {'people': item.limit_people_count})}} {{ itemCurrency }}{{ item.valid_price }} {{ itemCurrency }}{{ item.invalid_price }} {{ itemDiscount }}

Ends in

{{ itemCurrency }}{{ priceFormat(item.valid_price / item.bundle_specification) }}/{{ item.unit }}

{{ itemCurrency }}{{ item.valid_price }} {{ itemCurrency }}{{ priceFormat(item.valid_price / item.bundle_specification) }}/{{ item.unit }} {{ itemCurrency }}{{ item.invalid_price }} {{itemDiscount}}

Sale ends in

Sale will starts after Sale ends in

{{ __( "Pay with Gift Card to get sale price: :itemCurrency:price", { 'itemCurrency' : itemCurrency, 'price' : (item.giftcard_price ? priceFormat(item.giftcard_price) : '0.00') } ) }} ({{ itemCurrency }}{{ priceFormat(item.giftcard_price / item.bundle_specification) }}/{{ item.unit }}) Details

Best before

Currently unavailable.

We don't know when or if this item will be back in stock.

Unavailable in your area.

Sold Out

Details

Full product details

Editer Recommend

著名理论计算机科学家Papadimitriou对计算复杂性全面而深刻的阐述，从事计算理论研究的研究生和相关人员的优秀参考书。

Content Description

计算机复杂理论的研究是计算机科学zui重要的研究领域之一，而Chistos.H.Papadimitriou是该领域zui著名的专家之一。本书是一本全面阐述计算机复杂性理论及其近年来进展的教科书，主要包含算法图灵机、可计算性等有关计算复杂理论的基本概念；布尔逻辑、一阶逻辑、逻辑中的不可判定性等复杂性理论的基础知识；P与NP、NP完全等各复杂性类的概念及其之间的关系等复杂性理论的核心内容；随机算法、近似算法、并行算法及其复杂性理论；以及NP之外如多项式空间等复杂性类的介绍。

Catalogue

Computational Complexity

出版者的话

译者序

前言

第一部分算法

第1章问题与算法

1.1图的可达性问题

1.2最大流问题

1.3旅行商问题

1.4注解、参考文献和问题

第2章图灵机

2.1图灵机概述

2.2视为算法的图灵机

2.3多带图灵机

2.4线性加速

2.5空间界

2.6随机存取机

2.7非确定性机

2.8注解、参考文献和问题

第3章不可判定性

3.1通用图灵机

3.2停机问题

3.3更多不可判定性问题

3.4注解、参考文献和问题

第二部分逻辑学

第4章布尔逻辑

4.1布尔表达式

4.2可满足性与永真性

4.3布尔函数与电路

4.4注解、参考文献和问题

第5章一阶逻辑

5.1一阶逻辑的语法

5.2模型

5.3永真的表达式

5.4公理和证明

5.5完备性定理

5.6完备性定理的推论

5.7二阶逻辑

5.8注解、参考文献和问题

第6章逻辑中的不可判定性

6.1数论公理

6.2作为一个数论概念的计算

6.3不可判定性与不完备性

6.4注解、参考文献和问题

第三部分P和NP

第7章复杂性类之间的关系

7.1复杂性类

7.2谱系定理

7.3可达性方法

7.4注解、参考文献和问题

第8章归约和完备性

8.1归约

8.2完全性

8.3逻辑特征

8.4注解、参考文献和问题

第9章NP完全问题

9.1NP中的问题

9.2可满足性问题的不同版本

9.3图论问题

9.4集合和数字

9.5注解、参考文献和问题

第10章coNP和函数问题

10.1NP和coNP

10.2素性

10.3函数问题

10.4注解、参考文献和问题

第11章随机计算

11.1随机算法

11.2随机复杂性类

11.3随机源

11.4电路复杂性

11.5注解、参考文献和问题

第12章密码学

12.1单向函数

12.2协议

12.3注解、参考文献和问题

第13章可近似性

13.1近似算法

13.2近似和复杂性

13.3不可近似性

13.4注解、参考文献和问题

第14章关于P和NP

14.1NP的地图

14.2同构和稠密性

14.3谕示

14.4单调电路

14.5注解、参考文献和问题

第四部分P内部的计算复杂性类

第15章并行计算

15.1并行算法

15.2计算的并行模型

15.3NC类

15.4RNC算法

15.5注解、参考文献和问题

第16章对数空间

16.1L=?NL问题

16.2交错

16.3无向图的可达性

16.4注解、参考文献和问题

第五部分NP之外的计算复杂性类

第17章多项式谱系

17.1优化问题

17.2多项式谱系

17.3注解、参考文献和问题

第18章有关计数的计算

18.1积和式

18.2P类

18.3注解、参考文献和问题

第19章多项式空间

19.1交错和博弈

19.2对抗自然的博弈和交互协议

19.3更多的PSPACE完全问题

19.4注解、参考文献和问题

第20章未来的展望

20.1指数时间复杂性类

20.2注解、参考文献和问题

索引

Introduction

我仅仅希望简单叙述请赋予我这一特权因为我们已经被灌输了带有这么多音乐的歌声音乐正在沉沦而我们的艺术变得如此矫饰以至于装饰品已经腐蚀了她的容颜是时候说一些简单的语言了因为明天我们的心灵将起帆远航——Giorgos Seferis本书适合作为低年级研究生或者高年级本科生学习计算复杂性理论的教材。计算复杂性是计算机科学中思考为什么有些问题用计算机难以解决的领域。这个领域以前几乎不存在，而现在却迅速扩展，并构成了理论计算机科学研究活动的主要内容。现在没有一本书可以全面介绍复杂性——当然也包括这本书在内。本书只是包含了我认为可以清楚和相对简单地表示的结果以及在我看来是复杂性领域的中心内容。
我认为复杂性是计算(复杂性类)和应用(问题)之间复杂而核心的部分。开篇就向读者灌输这一观点有点为时过早，不过我还是要冒险一试，而且这也将是全书20章中反复强调的观点。完全性的结论明显是这一进展的中心环节。逻辑也是如此，它能很好地表达和抓住计算这一概念，是非常重要的应用。因此计算、问题和逻辑是贯穿本书的三大主脉络。
内容快速浏览目录，第1章介绍问题和算法——因为当复杂性与简单性比较时，复杂性最好理解。第2章讨论图灵机，同时明确我们的方式将不依赖于机器。第3章介绍非确定性（它不仅是复杂性的最高形式，而且还具有重大的方法学影响）。
接着讨论逻辑。这一部分最可能会被复杂性理论同行视为另类。但是它对于我看待复杂性的观点非常重要，对于计算机科学非常基本，又很少作为走向计算机科学家的成功之路看待，所以我感到我必须做一次尝试。第4章介绍布尔逻辑（包括Horn子句的算法属性，以及布尔电路和香农定理）。第5章介绍一阶逻辑及其模型论和证明论，还包括完全性定理，以及足够的二阶逻辑以引出随后的NP的Fagin特征——非常有用但是往往被忽视，其意义相当于Cook定理。第6章是对Gdel不完全性定理的独立证明，该证明是逻辑表达计算早期的重要例子。
然后重点介绍复杂性。第7章介绍已知的复杂性类之间的关系——包括Savitch和 ImmermanSzelepscényi关于空间复杂性的定理。第8章介绍归约和完全性概念，紧接着，作为例子，介绍Cook定理和电路值问题的P完全性，同时比较用逻辑表示P和NP的特征。第9章包含很多NP完全的结果，同时介绍各种证明方法。第10章讨论coNP和函数问题。第11章介绍随机算法、与之对应的复杂性类以及用现实随机源的实现方法。电路和它们与复杂性、随机化的关系也在此介绍。第12章很简短，粗略介绍密码学和协议。第13章讨论近似算法，以及最近通过概率可验证性证明得出的一些不可行性方面的结果。另一方面，第14章讨论P=?NP问题的结构性方面，比如，中间度、同构、稠密性和谕示。它还包含了Razborov关于单调电路的下界证明。
第15章进一步关注P、并行算法及其复杂性，第16章重点讨论对数空间，包括无向图路径的随机游走算法。最后，除了NP以外，第17章给出多项式谱系（包括优化问题的Krentel特征）；第18章讲述计数问题和关于积和式的Valiant定理；第19章介绍多项式空间的许多方面（最有趣的是关于交互式协议的Shamir定理）；本书最后对难解性领域做了简短展望。
本书并没有特别的数学基础要求——除了要有一定程度的“数学成熟度”，而数学成熟度这个名词，一般不在序言中给予定义。所有的定理都从基本原理给予证明（除了第13章关于近似性引用了两个定理外），同时更多的相关结果在每章最后一节中说明。证明和构造经常会比文献里讲述的简单得多。实际上，本书包含了多个与复杂性相关的主题或专题简介：基础数论（用来证明Pratt定理），SolovayStrassen素数测定和RSA密码协议（第10、11、12章）；基础概率（第11章和其他章节）；组合数学和概率方法（第10、13、14章）；递归理论（第3、14章）；逻辑（第4、5、6章）。由于复杂性问题总是和相对应的算法概念的全面发展联系在一起（第1章的有效算法，第11章的随机算法，第13章的近似算法和第15章的并行算法），所以本书也可以作为算法引论——虽然仅仅粗略分析，但是可以应用在各种情况。
注解和问题每章的最后一节包含了相关的文献、注解、练习和问题。很多问题涉及更深的结论和课题。就我看来，这是一章中最重要的部分（经常也是最长的），读者应该将它作为本书的一部分来阅读。它经常给出历史观点，并把该章放到了更广泛的领域中。所有这些题目都是可做的，至少在提示下去图书馆查阅答案（我已经发现这样做至少对我的学生来说，不亚于另一次智商测验）。对这些题目没有标记难易，不过对于真正的难题还是给出了警示标记。
教学本书的重点显然是复杂性，所以我们将它设计成（以及用作）计算机科学家关于计算理论的入门级读物。我和我的同事在过去的三年中用它作为加州大学圣地亚哥分校硕士研究生第一年为期10周的教材。前两周学习前4章，这些内容对于本科生来说，一般都已熟悉。逻辑学安排在紧接着的3周中，经常省略完全性证明。剩下的5周学习第7章，作为NP完全性的严格训练（不包括在该校的算法课内），选择第11～14章中的一两节。一学期的课程可以涵盖以上4章。如果你想跳过逻辑学部分，可以加上第15章（然而，我相信这样做会错过本书相当好的一部分内容）。
本书至少还可以用于两门课程：前9章的主题对于计算机科学家很关键，所以它可以自豪地替代高年级本科生初级理论课程中的自动机和形式语言（特别是，因为现在的编译课程都已独立出来）。我也两次使用后面的11章作为理论方向的第二学期课程，其目标是带领有兴趣的研究生进入复杂性的研究课题——或者至少帮助他们成为计算机理论会议上见多识广的听众。
感谢我关于复杂性的想法是我的老师、学生和同事长期鼓舞和启迪的结果。我非常感谢所有这些人：Ken Steiglitz、Jeff Ullman、Dick Karp、Harry Lewis、John Tsitsiklis、Don Knuth、Steve Vavasis、Jack Edmonds、Albert Meyer、Gary Miller、Patrick Dymond、Paris Kanellakis、David Johnson、Elias Koutsoupias（他也在图表、最后检查和索引上给予我很多帮助）、Umesh Vazirani、Ken Arrow、Russell Impagliazzo、Sam Buss、Milena Mihail、Vijay Vazirani、Paul Spirakis、Pierluigi Crescenzi、Noga Alon、Stathis Zachos、Heather Woll、Phokion Kolaitis、Neil Immerman、Pete Veinott、Joan Feigenbaum、Lefteris Kirousis、Deng Xiaotie、Foto Afrati、Richard Anderson，最主要的是Mihalis Yannakakis和Mike Sipser。他们阅读了本书的草稿并提出了建设性意见、想法和建议——否则就会让我为他们的沉默而紧张。在所有对我的课件提出评论的学生中，我记得名字的只有David Morgenthaller、Goran Gogic、Markus Jacobsson和George Xylomenos（但我记住了其余人的笑容）。最后，感谢Richard Beigel、Matt Wong、Wenhong Zhu和他们在耶鲁的复杂性班，他们找出了本书初稿中的许多错误。自然，我对剩下的错误负责——尽管我认为我的朋友当初可以找出更多的错误。
我非常感激Martha Sideri的鼓励和支持，以及她的注解、看法和封面设计。
我在加州大学圣地亚哥分校工作时完成本书，但这期间我也访问了AT&T公司的贝尔实验室、Bonn大学、Saarbrücken的MaxPlanck研究所、Patras大学和那里的计算机学院以及巴黎 Sud 大学。我对于算法和复杂性的研究受到美国国家科学基金、Esprit项目AlCOM以及加州大学圣地亚哥分校信息和计算机科学主席Irwin Mark和Joan Klein Jacobs的资助。
与Addison Wesley的Tom Stone及其同事一起完成本书出版是愉快的。最后，我使用了Don Knuth的TeX排版，我的宏是从Jeff Ullman很多年前给我的那些中演变而来的。
Christos H.Papadimitriou

alt="" />

Specifications

Brand

Jingdong book

Brand Origin

China

Disclaimer

Product packaging, specifications and price are subject to change without notice. All information about the products on our website is provided for information purposes only. Please always read labels, warnings and directions provided with the product before use.

View Full Terms of Use

Scan to Share

Add to favorites

{{ $isZh ? coupon.coupon_name_sub : coupon.coupon_ename_sub | formatCurrency }}

Clip coupons

Quantity

{{buttonTypePin == 3 ? __("Scan to view more PinGo") : __("Scan to start")}}

Sold by JD@CHINA

Ship to

Free shipping over 69

Genuine guarantee

View details

Region

Added to Cart

Keep Shopping

More to Consider

Coupons

Clip Clipped Over

Expires soon {{ formatTime(coupon.use_end_time) }}

Share this item with friends

Cancel

Yami Gift Card

Get this exclusive deal when paying with gift card

Terms and Conditions

Gift card deals are special offers for selected products;

The gift card deals will automatically be activated if a customer uses gift card balance at check out and the balance is sufficient to pay for the total price of the shopping cart products with gift card deals;

You will not be able to activate the gift card deals if you choose other payment methods besides gift card. The products will be purchased at their normal prices;

If your account balance is not enough to pay for the products with gift card deals, you can choose to reload your gift card balance by clicking on the Reload button at either shopping cart page or check out page;

Products that have gift card deals can be recognized by a special symbol showing 'GC Deal';

For any additional questions or concerns, please contact our customer service;

Yamibuy reserves the right of final interpretation.

Sold by Yami

Service Guarantee

Free Shipping over $49

Easy Returns

Ships from United States

Shipping

United States

Standard Shipping is $5.99 (Excluding Alaska & Hawaii). Free on orders of $49 or more.

Local Express is $5.99 (Available in Parts of CA, NJ, MA & PA). Free on orders of $49 or more.

2-Day Express (Includes Alaska & Hawaii) starts at $19.99.

Return Policy

Yami is committed to provide our customers with a peace of mind when purchasing from us. Most items shipped from Yamibuy.com can be returned within 30 days of receipt of shipment (For Food, Beverages, Snacks, Dry Goods, Health supplements, Fresh Grocery and Perishables Goods, within 7 days of receipt of shipment due to damages or quality issues; To ensure that every customer receives safe and high-quality products, we do not provide refunds or returns for beauty products once they have been opened or used, except in the case of quality issues; Some products may have different policies or requirements associated with them, please see below for products under special categories, or contact Yami Customer Service for further assistance).
Thank you for your understanding and support.

Learn More

Sold by Yami

Terms and Conditions of Yami E-Gift Card

If you choose “Redeem automatically” as your delivery method, your gift card balance will be reload automatically after your order has been processed successfully;

If you choose “Send to Email”as your delivery method, the card number and CVV will be sent to the email address automatically;

Any user can use the card number and CVV to redeem the gift card, please keep your gift card information safely. If you have any trouble receiving email, please contact Yami customer service;

Yami gift card can be used to purchase both Yami owned or Marketplace products;

Yami gift card will never expire;

Yami gift card balance does not have to be used up at once;

Return Policy

Gift card that has already been consumed is non-refundable.

Sold by JD@CHINA

Fulfilled by Yami

Service Guarantee

Free Shipping over $49

Easy Returns

Ships from United States

Shipping

United States

Standard Shipping is $5.99 (Excluding Alaska & Hawaii). Free on orders of $49 or more.

Local Express is $5.99 (Available in Parts of CA, NJ, MA & PA). Free on orders of $49 or more.

2-Day Express (Includes Alaska & Hawaii) starts at $19.99.

Return Policy

You may return product within 30 days upon receiving the product. Items returned must be new in it's original packing, including the original invoice for the purchase. Customer return product at their own expense.

Sold by JD@CHINA

Yami-China FC

Service Guarantee

Cross-store Free Shipping over $69

30-days Return

Yami-China FC

Yami has a consolidation warehouse in China which collects multiple sellers’ packages and combines to one order. Our Yami consolidation warehouse will directly ship the packages to your door. Cross-store free shipping over $69.

Return Policy

You may return products within 30 days upon receiving the products. Sellers take responsibilities for any wrong shipment or missing items. Packing needs to be unopened for any other than quality issues return. We promise to pack carefully, but because goods are taking long journey to destinations, simple damages to packaging may occur. Any damages not causing internal goods quality problems are not allowed to return. If you open the package and any quality problem is found, please contact customer service within three days after receipt of goods.

Shipping Information

Yami Consolidation Service Shipping Fee $9.99(Free shipping over $69)

Sellers in China will ship their orders within 1-2 business days once the order is placed. Packages are sent to our consolidation warehouse in China and combined there. Our Yami consolidation warehouse will directly ship the packages to you via UPS. The average time for UPS to ship from China to the United States is about 10 working days and it can be traced using the tracking number. Due to the pandemic, the delivery time may be delayed by about 5 days. The package needs to be signed by the guest. If the receipt is not signed, the customer shall bear the risk of loss of the package.

Sold by JD@CHINA

Service Guarantee

Free shipping over 69

Genuine guarantee

Shipping

Yami Consolidated Shipping $9.99(Free shipping over $69)

Seller will ship the orders within 1-2 business days. The logistics time limit is expected to be 7-15 working days. In case of customs clearance, the delivery time will be extended by 3-7 days. The final receipt date is subject to the information of the postal company.

Yami Points information

All items are excluding from any promotion or points events on Yamibuy.com

Return Policy

Download the Yami App

Feedback

Back Top

Reviews{{'('+ commentList.posts_count + ')'}}

Have your say. Be the first to help other guests.

Write a review

{{i}} star

{{i}} stars

{{ parseInt(commentRatingList[i]) }}%

{{ showTranslate(comment) }}Show Less

{{ strLimit(comment,800) }}Show more

Show Original

Show All

{{ formatTime(comment.in_dtm) }} VERIFIED PURCHASE {{groupData}}

{{ comment.likes_count }} {{ comment.likes_count }} {{ comment.reply_count }} {{comment.in_user==uid ? __('Delete') : __('Report')}}

{{ showTranslate(comment) }}Show Less

{{ strLimit(comment,800) }}Show more

Show Original

Show All

{{ formatTime(comment.in_dtm) }} VERIFIED PURCHASE {{groupData}}

{{ comment.likes_count }} {{ comment.likes_count }} {{ comment.reply_count }} {{comment.in_user==uid ? __('Delete') : __('Report')}}

No related comment~

Load more reviews

Review

{{ showTranslate(commentDetails) }}Show Less

{{ strLimit(commentDetails,800) }}Show more

Show Original

Show All

{{ formatTime(commentDetails.in_dtm) }} VERIFIED PURCHASE {{groupData}}

Please write at least one word

Comments{{'(' + replyList.length + ')'}}