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

Ján Pich

doi:10.2168/LMCS-11(2:8)2015

Ján Pich - 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 - https://doi.org/10.2168/LMCS-11(2:8)2015

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

Authors: Ján Pich

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.

https://doi.org/10.2168/LMCS-11(2:8)2015

Source: arXiv.org:1412.3246

Volume: Volume 11, Issue 2

Published on: June 16, 2015

Submitted on: June 29, 2014

Keywords: Mathematics - Logic,Computer Science - Computational Complexity

Licence: arXiv.org - Non-exclusive license to distribute

Bibliographic References

33 Documents citing this article

Jiatu Li;Igor C. Oliveira, Warwick Research Archive Portal (University of Warwick), Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic, 2023, Orlando FL USA, 10.1145/3564246.3585144, http://wrap.warwick.ac.uk/174718/1/WRAP-Unprovability-of-strong-complexity-lower-bounds-in-bounded-arithmetic-Oliveira-2023.pdf.

Rahul Ilango;Jiatu Li;R. Ryan Williams, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic, 2023, Orlando FL USA, 10.1145/3564246.3585187.

Abhishek Jain;Zhengzhong Jin, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), Indistinguishability Obfuscation via Mathematical Proofs of Equivalence, 2022, Denver, CO, USA, 10.1109/focs54457.2022.00100.

Leszek Aleksander Kolodziejczyk;Neil Thapen, 2022, Approximate counting and NP search problems, arXiv (Cornell University), 22, 03, 10.1142/s021906132250012x, http://arxiv.org/abs/1812.10771.

Marco Carmosino;Valentine Kabanets;Antonina Kolokolova;Igor Carboni Oliveira, Warwick Research Archive Portal (University of Warwick), LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic, 2022, Denver, CO, USA, 10.1109/focs52979.2021.00080, http://wrap.warwick.ac.uk/158167/1/WRAP-LEARN-uniform-circuit-lower-bounds-provability-bounded-arithmetic-Carboni-Oliveira-2021.pdf.

Moritz Martin Muller;Ján Pich, 2020, Feasibly constructive proofs of succinct weak circuit lower bounds, Annals of Pure and Applied Logic, 171, 2, pp. 102735, 10.1016/j.apal.2019.102735, https://doi.org/10.1016/j.apal.2019.102735.

Cambridge University Press eBooks, Resolution, pp. 93-114, 2019, 10.1017/9781108242066.007.

Cambridge University Press eBooks, LKd+1/2 and Combinatorial Restrictions, pp. 296-305, 2019, 10.1017/9781108242066.016.

Cambridge University Press eBooks, Further Proof Systems, pp. 134-162, 2019, 10.1017/9781108242066.009.

Cambridge University Press eBooks, Bibliography, pp. 481-505, 2019, 10.1017/9781108242066.025.

2019, Index, Cambridge University Press eBooks, pp. 510-516, 10.1017/9781108242066.026.

Cambridge University Press eBooks, The Nature of Proof Complexity, pp. 472-480, 2019, 10.1017/9781108242066.024.

Cambridge University Press eBooks, Basic Example of the Correspondence between Theories and Proof Systems, pp. 165-184, 2019, 10.1017/9781108242066.010.

Cambridge University Press eBooks, Feasible Interpolation: A Framework, pp. 353-383, 2019, 10.1017/9781108242066.019.

Cambridge University Press eBooks, Up to EF via the 〈. . .〉 Translation, pp. 197-210, 2019, 10.1017/9781108242066.012.

Cambridge University Press eBooks, Introduction, pp. 1-8, 2019, 10.1017/9781108242066.002.

Cambridge University Press eBooks, Optimality, pp. 456-471, 2019, 10.1017/9781108242066.023.

Cambridge University Press eBooks, Hard Tautologies, pp. 413-441, 2019, 10.1017/9781108242066.021.

Cambridge University Press eBooks, The Two Worlds of Bounded Arithmetic, pp. 185-196, 2019, 10.1017/9781108242066.011.

Cambridge University Press eBooks, Examples of Upper Bounds and p-Simulations, pp. 211-232, 2019, 10.1017/9781108242066.013.

Cambridge University Press eBooks, Model Theory and Lower Bounds, pp. 442-455, 2019, 10.1017/9781108242066.022.

Cambridge University Press eBooks, Fd and Logical Restrictions, pp. 306-336, 2019, 10.1017/9781108242066.017.

2019, Preface, Proof Complexity, pp. xiii-xiv, 10.1017/9781108242066.001.

Cambridge University Press eBooks, Frege Systems, pp. 39-63, 2019, 10.1017/9781108242066.004.

Cambridge University Press eBooks, Feasible Interpolation: Applications, pp. 384-410, 2019, 10.1017/9781108242066.020.

Cambridge University Press eBooks, Algebraic and Geometric Proof Systems, pp. 337-352, 2019, 10.1017/9781108242066.018.

Cambridge University Press eBooks, R and R-Like Proof Systems, pp. 263-295, 2019, 10.1017/9781108242066.015.

Cambridge University Press eBooks, Concepts and Problems, pp. 11-38, 2019, 10.1017/9781108242066.003.

Cambridge University Press eBooks, Sequent Calculus, pp. 64-80, 2019, 10.1017/9781108242066.005.

Jan Krajíček, Cambridge University Press eBooks, Quantified Propositional Calculus, pp. 81-92, 2019, 10.1017/9781108242066.006.

Jan Krajíček, Cambridge University Press eBooks, Algebraic and Geometric Proof Systems, pp. 115-133, 2019, 10.1017/9781108242066.008.

Jan Krajíček, Cambridge University Press eBooks, Beyond EF via the || . . . || Translation, pp. 233-260, 2019, 10.1017/9781108242066.014.

Jan Krajíček, 2019, Proof Complexity, 10.1017/9781108242066.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 1100 times.

This article's PDF has been downloaded 331 times.