计算复杂性

计算机复杂理论的研究是计算机科学最重要的研究领域之一，而Chistos.H.Papadimitriou是该领域最著名的专家之一。本书是一本全面阐述计算机复杂性理论及其近年来进展的教科书，主要包含算法图灵机、可计算性等有关计算复杂理论的基本概念；布尔逻辑、一阶逻辑、逻辑中的不可判定性等复杂性理论的基础知识；P与NP、NP完全等各复杂性类的概念及其之间的关系等复杂性理论的核心内容；随机算法、近似算法、并行算法及其复杂性理论；以及NP之外如多项式空间等复杂性类的介绍。

克里斯特斯 H.帕帕季米特里乌（Christos H.Papadimitriou）是当今计算机科学界最活跃和有影响力的科学家之一。Papadimitriou拥有普林斯顿大学博士学位，现为加州大学伯克利分校计算机科学系教授。他曾在哈佛大学、麻省理工学院、雅典工艺大学、斯坦福大学、加州大学圣地亚哥分校任教。他是美国科学院院士、美国工程院院士和美国人文科学院院士。他于2002年获得高德纳奖，2012年获得哥德尔奖。他的主要研究领域是算法和复杂性，以及它们在优化、数据库、人工智能、经济和互联网等方面的应用，曾撰写此领域教科书5本，发表论文数篇。