123,123

內(nèi)容簡(jiǎn)介

　　本書介紹計(jì)算復(fù)雜性理論的一個(gè)重要部分：判定權(quán)理論。全部?jī)?nèi)容圍繞該理論中的一個(gè)重要且未解決的問題：Karp猜想。全書分九講。前四講介紹判定權(quán)的一般理論及Karp猜想的提出背景。五至八講介紹研究Karp猜想的方法及已存在的成果。最后一講介紹隨機(jī)判定樹以及其中的Yar：Karp猜想。作者試圖通過對(duì)這一具體問題的詳盡剖析，向讀者展示計(jì)算復(fù)雜性理論的思想方法和意義，并將讀者引入研究的前沿。本書是為數(shù)學(xué)以及理論計(jì)算機(jī)科學(xué)專業(yè)的研究生和高年級(jí)的大學(xué)生所寫的通俗讀物，對(duì)從事這方面工作的教師與科技工作者也有參考價(jià)值。

作者簡(jiǎn)介

　　堵丁柱，黑龍江齊齊哈爾人，1948年5月生。1977年考入齊齊哈爾經(jīng)工學(xué)院，1978年后隨導(dǎo)師越民義分入應(yīng)用數(shù)學(xué)所。1982年獲碩士學(xué)位并赴美攻讀博士。1985年于加里福尼亞大學(xué)圣巴巴拉分校獲數(shù)學(xué)博士。先后工作于伯克利數(shù)學(xué)科學(xué)研究所、麻省理工學(xué)院以及普林斯頓大學(xué)。現(xiàn)為中國科學(xué)院應(yīng)用數(shù)學(xué)所研究員，同時(shí)為美國明尼蘇達(dá)大學(xué)計(jì)算機(jī)科學(xué)系正教授。自1980年從事應(yīng)用數(shù)學(xué)研究以來，在國內(nèi)外發(fā)表論文百余篇，并著有《可行方向方法的收劍理論》和《組合群試的理論與應(yīng)用》（與黃光明合著）?，F(xiàn)任《組合優(yōu)化雜志》（英文）主編和《組合優(yōu)化從書》（英文）主編。

圖書目錄

第一講　布爾函數(shù)與判定樹
1.1　布爾函數(shù)
1.2　圖與圖性質(zhì)
1.3　判定樹
練習(xí)題
第二講　下界與上界
2.1　隱子與子句
2.2　界
2.3　弱對(duì)稱函數(shù)
練習(xí)題
第三講　詭函數(shù)
3.1　代數(shù)判別法
3.2　弱對(duì)稱詭函數(shù)
3.3　一個(gè)反例
練習(xí)題
第四講　圖性質(zhì)
4.1　幾個(gè)例子
4.2　Karp猜想
4.3　團(tuán)與染色
練習(xí)題
第五講　拓?fù)浞椒?
5.1　單純復(fù)形與歐拉示性數(shù)
5.2　可塌性
5.3　拓?fù)渑袆e法
練習(xí)題
第六講不動(dòng)點(diǎn)的妙用
6.1　不動(dòng)點(diǎn)定理
6.2　單純映象
6.3　二分圖的性質(zhì)
練習(xí)題
第七講　置換群的應(yīng)用
7.1　自同構(gòu)群的不動(dòng)點(diǎn)
7.2　Wreath積
7.3　單調(diào)圖性質(zhì)
練習(xí)題
第八講　六階圖
8.1　驗(yàn)證Karp猜想
8.2　對(duì)有向圖的注記
8.3　啟迪與思考
練習(xí)題
第九講　隨機(jī)判定樹
9.1　定義
9.2　下界
9.3　Yar-Karp猜想
練習(xí)題
后記
參考文獻(xiàn)