可計算性和計算複雜性

內容介紹

本書深入淺出地介紹了研究可計算性的四個主要模型以及四個模型彼此之間的關係：介紹了計算複雜性的基本概念和重要的研究方法與一些研究成果。內容涉及遞歸函式、圖靈機、λ演算、馬爾可夫算法、計算複雜度的分類、NP完全理論、非一致複雜性等。分述於十章,書中附有習題。
本書可作為廣大有志於突破計算複雜性研究僵局——“P=NP？”的科技工作者,計算機科學和元計算機科學工作者,數學和元數學工作者以及大專院校的教師和學生的入門書、教材和參考書,亦可作為計算機基礎理論的參考書。