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