《計(jì)算復(fù)雜性導(dǎo)論》可用作計(jì)算機(jī)專業(yè)、計(jì)算數(shù)學(xué)專業(yè)的計(jì)算機(jī)理論課程的教材，也是有關(guān)研究人員不可或缺的參考書。計(jì)算復(fù)雜性理論是用數(shù)學(xué)方法研究使用數(shù)位計(jì)算機(jī)解決各種算法問題困難度的理論?！队?jì)算復(fù)雜性導(dǎo)論》對(duì)計(jì)算機(jī)科學(xué)中這一重要理論做了全面的介紹。其內(nèi)容包含基本理論，如計(jì)算模型NP-完全性，以及較深入的課題，如線路復(fù)雜性、概率復(fù)雜性和交互證明系統(tǒng)等。此外，《計(jì)算復(fù)雜性導(dǎo)論》還包括了復(fù)雜性理論近年來兩個(gè)較重大的突破，即概率可驗(yàn)證明及其在近似算法上的應(yīng)用和平均NP-完全理論?！队?jì)算復(fù)雜性導(dǎo)論》中所有結(jié)果均有嚴(yán)格的數(shù)學(xué)證明，在每章后配有相關(guān)練習(xí)題。