計算復雜性理論是研究各種計算模型、探究各種計算問題求解有效算法的存在性、比較計算問題求解的困難程度并據(jù)其復雜度進行分類研究的理論。本書對這些基礎(chǔ)理論知識進行了全面介紹。在此基礎(chǔ)上，引入了格的LLL算法、最近平面算法和格的某些困難問題的相關(guān)復雜度研究結(jié)果，并進一步介紹計算復雜性在密碼學中的應(yīng)用，嘗試為讀者呈現(xiàn)計算復雜性理論和密碼學相融合的知識體系，特別適合于從事密碼學尤其是從事基于格的后量子密碼研究的讀者。