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, https://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, DSpace@MIT (Massachusetts Institute of Technology), Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic, 5, pp. 1076-1089, 2023, Orlando FL USA, 10.1145/3564246.3585187, https://hdl.handle.net/1721.1/151005.

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 Kołodziejczyk;Neil Thapen, 2022, Approximate counting and NP search problems, arXiv (Cornell University), 22, 03, 10.1142/s021906132250012x, https://arxiv.org/abs/1812.10771.

Marco Carmosino;Valentine Kabanets;Antonina Kolokolova;Igor C. 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.

Jan Krajíček, Cambridge University Press eBooks, Resolution, pp. 93-114, 2019, 10.1017/9781108242066.007.

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

Jan Krajíček, Cambridge University Press eBooks, Further Proof Systems, pp. 134-162, 2019, 10.1017/9781108242066.009.

Jan Krajíček, Cambridge University Press eBooks, Bibliography, pp. 481-505, 2019, 10.1017/9781108242066.025.

Jan Krajíček, 2019, Index, Cambridge University Press eBooks, pp. 510-516, 10.1017/9781108242066.026.

Jan Krajíček, Cambridge University Press eBooks, The Nature of Proof Complexity, pp. 472-480, 2019, 10.1017/9781108242066.024.

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

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, Feasible Interpolation: A Framework, pp. 353-383, 2019, 10.1017/9781108242066.019.

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

Jan Krajíček, Cambridge University Press eBooks, Introduction, pp. 1-8, 2019, 10.1017/9781108242066.002.

Jan Krajíček, Cambridge University Press eBooks, Optimality, pp. 456-471, 2019, 10.1017/9781108242066.023.

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, Hard Tautologies, pp. 413-441, 2019, 10.1017/9781108242066.021.

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

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

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

Jan Krajíček, Cambridge University Press eBooks, Model Theory and Lower Bounds, pp. 442-455, 2019, 10.1017/9781108242066.022.

Jan Krajíček, Cambridge University Press eBooks, Fd and Logical Restrictions, pp. 306-336, 2019, 10.1017/9781108242066.017.

Jan Krajíček, 2019, Preface, Proof Complexity, pp. xiii-xiv, 10.1017/9781108242066.001.

Jan Krajíček, Cambridge University Press eBooks, Frege Systems, pp. 39-63, 2019, 10.1017/9781108242066.004.

Jan Krajíček, Cambridge University Press eBooks, Feasible Interpolation: Applications, pp. 384-410, 2019, 10.1017/9781108242066.020.

Jan Krajíček, Cambridge University Press eBooks, Algebraic and Geometric Proof Systems, pp. 337-352, 2019, 10.1017/9781108242066.018.

Jan Krajíček, Cambridge University Press eBooks, R and R-Like Proof Systems, pp. 263-295, 2019, 10.1017/9781108242066.015.

Jan Krajíček, Cambridge University Press eBooks, Concepts and Problems, pp. 11-38, 2019, 10.1017/9781108242066.003.

Jan Krajíček, Cambridge University Press eBooks, Sequent Calculus, pp. 64-80, 2019, 10.1017/9781108242066.005.

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

Moritz Müller;Ján Pich, 2019, 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.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 1529 times.

This article's PDF has been downloaded 380 times.