計算復雜性

計算機復雜理論的研究是計算機科學最重要的研究領(lǐng)域之一，而Chistos.H.Papadimitriou是該領(lǐng)域最著名的專家之一。本書是一本全面闡述計算機復雜性理論及其近年來進展的教科書，主要包含算法圖靈機、可計算性等有關(guān)計算復雜理論的基本概念；布爾邏輯、一階邏輯、邏輯中的不可判定性等復雜性理論的基礎(chǔ)知識；P與NP、NP完全等各復雜性類的概念及其之間的關(guān)系等復雜性理論的核心內(nèi)容；隨機算法、近似算法、并行算法及其復雜性理論；以及NP之外如多項式空間等復雜性類的介紹。

克里斯特斯 H.帕帕季米特里烏（Christos H.Papadimitriou）是當今計算機科學界最活躍和有影響力的科學家之一。Papadimitriou擁有普林斯頓大學博士學位，現(xiàn)為加州大學伯克利分校計算機科學系教授。他曾在哈佛大學、麻省理工學院、雅典工藝大學、斯坦福大學、加州大學圣地亞哥分校任教。他是美國科學院院士、美國工程院院士和美國人文科學院院士。他于2002年獲得高德納獎，2012年獲得哥德爾獎。他的主要研究領(lǐng)域是算法和復雜性，以及它們在優(yōu)化、數(shù)據(jù)庫、人工智能、經(jīng)濟和互聯(lián)網(wǎng)等方面的應用，曾撰寫此領(lǐng)域教科書5本，發(fā)表論文數(shù)篇。