本書介紹了計算復(fù)雜性理論的一些基礎(chǔ)知識，如計算模型Turing 機、復(fù)雜性的度量與本質(zhì)關(guān)系、P等不等于NP問題、空間復(fù)雜性等，還選擇了一些適合密碼學(xué)及信息安全專業(yè)學(xué)習的高級專題，如隨機化算法、電路復(fù)雜性、交互式證明等進行了介紹。
本書的編寫盡量少使用計算機專業(yè)術(shù)語，涉及的計算問題相對集中，避免學(xué)生因相關(guān)數(shù)學(xué)知識儲備不夠而造成困惑。對較難的定理證明，給出直觀分析以增進學(xué)生的理解和消化。設(shè)置了合適數(shù)量和難度的習題，習題中的知識點也非常重要，通過給出適當提示，引導(dǎo)學(xué)生完成。
本書可作為密碼學(xué)、信息安全及相關(guān)專業(yè)的計算復(fù)雜性理論課程的教材。