ISBN：10位［7535526004］13位［9787535526007］
出版社：湖南教育出版社
出版日期：1998年
定價：￥6.20元
內容提要
本書介紹計算複雜性理論的一個重要部分----判定權理論。全部內容圍繞該理論中的一個重要且未解決的問題----Karp猜想。
全書分九講。前四講介紹判定權的一般理論及Karp猜想的提出背景。五至八講介紹研究Karp猜想的方法及已存在的成果。最後一講介紹隨機判定樹以及其中的Yar----Karp猜想。作者試圖通過對這一具體問題的詳盡剖析，向讀者展示計算複雜性理論的思想方法和意義，並將讀者引入研究的前沿。本書是為數學以及理論計算機科學專業的研究生和高年級的大學生所寫的通俗讀物，對從事這方面工作的教師與科技工作者也有參考價值。
編輯推薦
本書介紹計算複雜性理論的一個重要部分----判定權理論。全部內容圍繞該理論中的一個重要且未解決的問題----Karp猜想。
全書分九講。前四講介紹判定權的一般理論及Karp猜想的提出背景。五至八講介紹研究Karp猜想的方法及已存在的成果。最後一講介紹隨機判定樹以及其中的Yar----Karp猜想。作者試圖通過對這一具體問題的詳盡剖析，向讀者展示計算複雜性理論的思想方法和意義，並將讀者引入研究的前沿。本書是為數學以及理論計算機科學專業的研究生和高年級的大學生所寫的通俗讀物，對從事這方面工作的教師與科技工作者也有參考價值。
作者簡介
堵丁柱，黑龍江齊齊哈爾人，1948年5月生。1977年考入齊齊哈爾經工學院，1978年後隨導師越民義分入套用數學所。1982年獲碩士學位並赴美攻讀博士。1985年於加里福尼亞大學聖巴巴拉分校獲數學博士。先後工作於伯克利數學科學研究所、麻省理工學院以及普林斯頓大學。現為中國科學院套用數學所研究員，同時為美國明尼蘇達大學計算機科學系正教授。
自1980年從事套用數學研究以來，在國內外發表論文百餘篇，並著有《可行方向方法的收劍理論》和《組合群試的理論與套用》（與黃光明合著）。現任《組合最佳化雜誌》（英文）主編和《組合最佳化從書》（英文）主編。
目錄
第一講 布爾函式與判定樹
1.1 布爾函式
1.2 圖與圖性質
1.3 判定樹
練習題
第二講 下界與上界
2.1 隱子與子句
2.2 界
2.3 弱對稱函式
練習題
第三講 詭函式
3.1 代數判別法
3.2 弱對稱詭函式
3.3 一個反例
練習題
第四講 圖性質
4.1 幾個例子
4.2 Karp猜想
4.3 團與染色
練習題
第五講 拓撲方法
5.1 單純復形與歐拉示性數
5.2 可塌性
5.3 拓撲判別法
練習題
第六講不動點的妙用
6.1 不動點定理
6.2 單純映象
6.3 二分圖的性質
練習題
第七講 置換群的套用
7.1 自同構群的不動點
7.2 Wreath積
7.3 單調圖性質
練習題
第八講 六階圖
8.1 驗證Karp猜想
8.2 對有向圖的註記
8.3 啟迪與思考
練習題
第九講 隨機判定樹
9.1 定義
9.2 下界
9.3 Yar-Karp猜想
練習題
後記
參考文獻
