Pich, Ján - Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic

lmcs:1568 - Logical Methods in Computer Science, June 16, 2015, Volume 11, Issue 2
Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic

Authors: Pich, Ján

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.


Source : oai:arXiv.org:1412.3246
DOI : 10.2168/LMCS-11(2:8)2015
Volume: Volume 11, Issue 2
Published on: June 16, 2015
Submitted on: June 29, 2014
Keywords: Mathematics - Logic,Computer Science - Computational Complexity


Share

Consultation statistics

This page has been seen 70 times.
This article's PDF has been downloaded 31 times.