The Cook-Reckhow definition
From MaRDI portal
Publication:6324919
DOI10.1145/3588287.3588arXiv1909.03691MaRDI QIDQ6324919FDOQ6324919
Authors: Jan Krajíček 
Publication date: 9 September 2019
Abstract: The Cook-Reckhow 1979 paper defined the area of research we now call Proof Complexity. There were earlier papers which contributed to the subject as we understand it today, the most significant being Tseitin's 1968 paper, but none of them introduced general notions that would allow to make an explicit and universal link between lengths-of-proofs problems and computational complexity theory. In this note we shall highlight three particular definitions from the paper: of proof systems, p-simulations and the pigeonhole principle formula, and discuss their role in defining the field. We will also mention some related developments and open problems.
This page was built for publication: The Cook-Reckhow definition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6324919)
