P/NP 問題是計(jì)算機(jī)科學(xué)乃至整個(gè)數(shù)學(xué)領(lǐng)域最重要的開放問題。本書從非技術(shù)角度介紹了什么是P/NP 問題、它豐富的歷史，以及對于人機(jī)交互乃至更多問題的數(shù)學(xué)意義。在這本趣味十足的書中，作者首先追溯了P/NP 問題是如何產(chǎn)生的，然后給出了這個(gè)問題的許多實(shí)例，涉及經(jīng)濟(jì)學(xué)、物理學(xué)和生物學(xué)在內(nèi)的多個(gè)學(xué)科。接下來探討了涵蓋P/NP 難題中所有難度等級的問題，從尋找游玩迪士尼樂園所有景點(diǎn)的最短路線，到地圖填色問題，再到找出Facebook 上互為好友的一群人。本書深入探尋了計(jì)算能夠做到什么、無法做到什么，描繪了嘗試解決P/NP問題的益處和其中難以預(yù)想的挑戰(zhàn)。
本書讀來引人入勝，適合所有對計(jì)算和數(shù)學(xué)感興趣的讀者。
作者簡介
Lance Fortnow
世界級計(jì)算機(jī)科學(xué)家，佐治亞理工學(xué)院計(jì)算機(jī)科學(xué)系教授、系主任，在計(jì)算復(fù)雜性和交互式證明系統(tǒng)領(lǐng)域取得了一系列重要研究成果，為計(jì)算機(jī)界所熟知。Fortnow早年師從著名的理論計(jì)算機(jī)科學(xué)家Michael Sipser，獲麻省理工學(xué)院應(yīng)用數(shù)學(xué)博士學(xué)位。畢業(yè)后曾在西北大學(xué)、芝加哥大學(xué)擔(dān)任教授，之前還做過NEC研究院高級研究員。他是知名博客Computational Complexity的創(chuàng)辦者，經(jīng)常與他人共同執(zhí)筆撰寫計(jì)算復(fù)雜性方面的文章。
目錄：
第1章 金券 1
維露卡的父親索爾特先生是個(gè)富商，他決定買光他能找到的巧克力。這還不夠，就算有堆積如山的巧克力，要從中找到小小的金券也很困難。
1.1 劃分的難題 3
1.2 手 4
1.3 P/NP問題 5
1.4 找到金券 6
1.5 漫漫長途 7
1.6 劃分難題的解 8
第2章 美妙的世界 10
“不完全準(zhǔn)確，”醫(yī)生說，“沒錯(cuò)，厄巴納算法幫人們戰(zhàn)勝了癌魔，治愈了艾滋病和糖尿病�？墒牵覀冞�不知道如何應(yīng)對普通感冒�！�
2.1 厄巴納算法 10
2.2 計(jì)算機(jī)1，癌癥0 13
2.3 棒球比賽 14
2.4 奧卡姆剃刀 17
2.5 創(chuàng)造力的自動(dòng)化 21
2.6 終極偵探 22
2.7 美妙世界的陰暗面 23
2.8 回到現(xiàn)實(shí) 24
第3章 P和NP 25
1852年，南非數(shù)學(xué)家弗朗西斯?格思里在為英國各郡的地圖填色時(shí)，猜想是否只用四種顏色，就足夠讓所有地圖上每兩個(gè)接壤的地區(qū)有不同的顏色。
3.1 敵友國 25
3.2 六度理論 25
3.3 牽線搭橋 28
3.4 團(tuán)問題 31
3.5 “遞棍兒” 32
3.6 刷房子 36
3.7 分組 38
3.8 P和NP 39
3.9 敵友國之外 40
3.10 Icosian游戲的一個(gè)解 43
第4章 NP中最難的問題 44
高德納對這個(gè)民選結(jié)果不太滿意，但也沒有覺得它差到讓人活不下去的地步。他本人特別想要找一個(gè)英文詞，既能捕捉“困難的搜索問題”這個(gè)直觀的意象，又要瑯瑯上口，便于向大眾普及。
4.1 第一個(gè)NP完全問題 44
4.2 21個(gè)問題 47
4.3 起個(gè)好名字有那么重要嗎 49
4.4 超越卡普的工作 51
4.5 漏網(wǎng)之魚 57
第5章 P和NP誕生前的歷史 62
圖靈在1936年就指出，圖靈機(jī)并不是什么都能計(jì)算。最著名的例子是停機(jī)問題，即沒有計(jì)算機(jī)能通過查看一段代碼就知道自己是會(huì)永遠(yuǎn)執(zhí)行下去還是會(huì)最終停止。
5.1 西方 63
5.2 東方 68
5.3 哥德爾的信 74
5.4 火星人法則 74
第6章 處理困難的問題 76
有時(shí)候一個(gè)問題天生排斥任何可能解決它的方法，對此你能做的只有放棄，然后去干點(diǎn)別的。
6.1 蠻力 77
6.2 啟發(fā)式方法 78
6.3 搜索小規(guī)模的解 83
6.4 近似計(jì)算方法 85
6.5 解決一個(gè)不同的問題 90
6.6 接受現(xiàn)實(shí) 92
6.7 總結(jié) 92
第7章 證明 94
2010年8月6日，惠普實(shí)驗(yàn)室的科學(xué)家維納里?德奧拉利卡向22位頂尖的理論計(jì)算機(jī)科學(xué)家發(fā)送了他寫的論文，題目簡潔有力：“ ”。
7.1 騙子悖論 95
7.2 電路 97
7.3 證明 時(shí)常犯的錯(cuò)誤 102
7.4 現(xiàn)狀 104
第8章 秘密 106
每個(gè)人都有秘密，從密碼到電子郵件，我們都有不想讓別人看到的東西。 意味著某些NP問題擁有不為人知的秘密，無法很快找到它的答案。
8.1 經(jīng)典密碼學(xué)簡史 106
8.2 現(xiàn)代密碼學(xué) 108
8.3 下的密碼學(xué) 111
8.4 零知識(shí)數(shù)獨(dú) 112
8.5 玩游戲 117
8.6 在云上進(jìn)行加密計(jì)算 119
8.7 創(chuàng)造隨機(jī)性 120
8.8 持續(xù)的挑戰(zhàn) 121
第9章 量子 123
即使有極小部分的量子和外界環(huán)境發(fā)生輕微作用而喪失了糾纏態(tài)，從另一頭出現(xiàn)的我就很可能被毀形，甚至變成一團(tuán)死肉。
9.1 量子錄像機(jī) 123
9.2 量子密碼學(xué) 127
9.3 量子隱形傳輸 128
9.4 量子的未來 132
第10章 未來 133
我本人對P/NP問題得到解決的前景持悲觀態(tài)度：我認(rèn)為 ，而且此生都看不到它的證明。
10.1 并行計(jì)算 133
10.2 處理大數(shù)據(jù) 135
10.3 一切事物的網(wǎng)絡(luò)化 136
10.4 應(yīng)對科技變革 137
10.5 關(guān)于P/NP問題的結(jié)束語 138
章節(jié)注釋和文獻(xiàn) 140
人名表 147
|
