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

Imported on: June 29, 2014

Keywords: Mathematics - Logic, Computer Science - Computational Complexity

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

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Bibliographic References

34 Documents citing this article

Erfan Khaniki, 2024, Jump Operators, Interactive Proofs and Proof Complexity Generators, 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pp. 573-593, 10.1109/focs61266.2024.00044.

Jiatu Li;Igor C. Oliveira, 2023, Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 1051-1057, 10.1145/3564246.3585144.

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

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

Leszek Aleksander Kołodziejczyk;Neil Thapen, 2022, Approximate counting and NP search problems, Journal of Mathematical Logic, 22, 03, 10.1142/s021906132250012x.

Marco Carmosino;Valentine Kabanets;Antonina Kolokolova;Igor C. Oliveira, 2022, LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic, Warwick Research Archive Portal (University of Warwick), pp. 770-780, 10.1109/focs52979.2021.00080.

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

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

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

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

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

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

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

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

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

Jan Krajíček, 2019, Proof Complexity, Cambridge University Press eBooks, 10.1017/9781108242066.

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

Jan Krajíček, 2019, Hard Tautologies, Cambridge University Press eBooks, pp. 413-441, 10.1017/9781108242066.021.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Jan Krajíček, 2019, Feasible Interpolation: A Framework, Cambridge University Press eBooks, pp. 353-383, 10.1017/9781108242066.019.

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.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 3040 times.

This article's PDF has been downloaded 722 times.