Logical Foundations of Proof Complexity

저자
Stephen Cook, Phuong Nguyen
출판사
Cambridge University Press
출판일
20210101
ISBN
9780521517294
ISBN 등록 지역
영어권 (ISBN 978-0)

소개

This book treats bounded arithmetic and propositional proof complexity from the point of view of computational complexity. The first seven chapters include the necessary logical background for the material and are suitable for a graduate course. Associated with each of many complexity classes are both a two-sorted predicate calculus theory, with induction restricted to concepts in the class, and a propositional proof system. The complexity classes range from AC0 for the weakest theory up t...