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