豆瓣
扫码直接下载
無敵
有点干,虽然我觉得还好,但也能理解为什么大家觉得如果没有背景知识不太好读。还是推荐 Introduction to the theory of computation.
坑
The bible of NP-Completeness
NP不会证明就看看这本吧。但是假如应付考试Algorithm Design那本就足够了。
我没读完过,读过前几章,能证明一些NP,但是还是搞不清楚SAT是怎么证的
就NP-hard的归约而言,这本书实在是太棒了,证明都很elegant。我印象最深的是关于3SAT NP-hard的proof,比Boaz和Sanjeev那本讲得好了太多,当然,Boaz那本比较适合真正要做research的人,这本对要做research人来说没什么用,都是很早之前的研究成果了。
经典老书;妈妈再也不用担心我证不出NP-hard了
The ultimate guide to NP-completeness
之前学长推荐看的,说几天就看完。我磨磨蹭蹭断断续续看了两三年。书有些年头,从现在的角度看gadget过于复杂有点过时。三四章讲计算问题研究整体思路还不错。附录里的问题很全面,一般当作字典用,常驻我的bib
finally 看懂 reduction from 3DM to 3SAT... 7 hours before the exam...
世界上最大的痛苦莫过于,知道你就在高维解空间里静静等待,但是我却无法在多项式时间内找到你
> Computers and Intractability
0 有用 壞人 2011-06-02 22:24:30
無敵
0 有用 Marine 2023-02-11 17:33:11 上海
有点干,虽然我觉得还好,但也能理解为什么大家觉得如果没有背景知识不太好读。还是推荐 Introduction to the theory of computation.
2 有用 zchenah 2017-12-31 14:07:08
坑
0 有用 ihatetopology 2020-04-04 09:41:39
The bible of NP-Completeness
0 有用 heisen 2019-03-31 03:47:46
NP不会证明就看看这本吧。但是假如应付考试Algorithm Design那本就足够了。
0 有用 noise 2014-01-04 11:51:04
我没读完过,读过前几章,能证明一些NP,但是还是搞不清楚SAT是怎么证的
3 有用 Chao 2015-11-29 02:57:44
就NP-hard的归约而言,这本书实在是太棒了,证明都很elegant。我印象最深的是关于3SAT NP-hard的proof,比Boaz和Sanjeev那本讲得好了太多,当然,Boaz那本比较适合真正要做research的人,这本对要做research人来说没什么用,都是很早之前的研究成果了。
2 有用 [已注销] 2014-09-01 17:30:53
经典老书;妈妈再也不用担心我证不出NP-hard了
0 有用 Philip 2010-06-22 04:37:55
The ultimate guide to NP-completeness
1 有用 ByebyePCP 2022-08-13 13:38:37
之前学长推荐看的,说几天就看完。我磨磨蹭蹭断断续续看了两三年。书有些年头,从现在的角度看gadget过于复杂有点过时。三四章讲计算问题研究整体思路还不错。附录里的问题很全面,一般当作字典用,常驻我的bib
1 有用 熙 2010-05-15 13:07:03
finally 看懂 reduction from 3DM to 3SAT... 7 hours before the exam...
3 有用 呱呱 2023-05-15 10:29:29 陕西
世界上最大的痛苦莫过于,知道你就在高维解空间里静静等待,但是我却无法在多项式时间内找到你