Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic

DOI10.2168/LMCS-11(2:8)2015zbMath1391.03028arXiv1412.3246OpenAlexW1614370253MaRDI QIDQ2941756

Ján Pich

Publication date: 25 August 2015

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.3246

zbMATH Keywords

bounded arithmeticcomplexity theoryformalizations

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Expander Construction in VNC1 ⋮ Approximate counting and NP search problems ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Unprovability of circuit upper bounds in Cook's theory PV

This page was built for publication: Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic