文章基本信息

标题：Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
本地全文：下载
作者：Ján Pich
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2015
卷号：11
期号：2
页码：1
DOI：10.2168/LMCS-11(2:8)2015
出版社：Technical University of Braunschweig
摘要：We present several known formalizations of theorems from computational complexity in bounded arithmetic and formalize the PCP theorem in the theory PV1 (no formalization of this theorem was known). This includes a formalization of the existence and of some properties of the (n,d,{\lambda})-graphs in PV1.
其他关键词：Bounded arithmetic, Complexity theory, Formalizations