[Proof Complexity] new preprint

[Jan Pich]

Dear colleagues,

I attach a new preprint of mine, titled "Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic". Comments, corrections, and suggestions are appreciated.

Best Wishes

Jan Pich

Abstract: We presenet several known formalizations of theorems from computational complexity in bounded arithmetic and formalize the PCP theorem in the theory $PV_1$ (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 $PV_1$.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pcpba.pdf
Type: application/pdf
Size: 528971 bytes
Desc: not available
URL: <http://list.math.cas.cz/pipermail/proof-complexity/attachments/20140629/451ae584/attachment-0001.pdf>