Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.
About 10,000 papers for “Proof complexity”
Krajíček, Jan · CERN Document Server (European Organization for Nuclear Research) · 2019
Offers a self-contained work presenting basic ideas, classical results, current state of the art and possible future directions in proof complexity.
Cited by 0
Krajíček, Jan 1960- · 2019
Cited by 0
Paul Beame · IAS/Park City mathematics series · 2004
Cited by 7
Jan Krajícek · 2004
This note, based on my 4ECM lecture, exposes few basic points of proof complexity in a way accessible to any mathematician.
Cited by 0
Jan Krajícek · 2008
This note, based on my 4ecm lecture, exposes few basic points of proof complexity in a way accessible to any mathematician.
Cited by 0
Princeton University Press eBooks · 2019
Cited by 0
Paul Beame · 2008
Cited by 0
Stefan Dantchev, Barnaby Martin, Stefan Szeider · Durham Research Online (Durham University) · 2007
We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional CNF formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter (we call such a formula a parameterized contradiction). One could separate the parameterized complexity classes FPT and W(M. Cesati, 2006) by showing that there is no fpt-bounded parameterized proof system, i.e., that there is no proof system that admits proofs of size f(k)n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(1)</sup> where f is a computable function and n represents the size of the propositional formula. By way of a first step, we introduce the system of parameterized tree-like resolution, and show that this system is not fpt-bounded. Indeed we give a general result on the size of shortest tree-like resolution proofs of parameterized contradictions that uniformly encode first-order principles over a universe of size n. We establish a dichotomy theorem that splits the exponential case of Riis's complexity-gap Theorem into two sub-cases, one that admits proofs of size f(k)n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(1)</sup> and one that does not. We also discuss how the set of parameterized contradictions may be embedded into the set of (ordinary) contradictions by the addition of new axioms. When embedded into general (DAG-like) resolution, we demonstrate that the pigeonhole principle has a proof of size 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sup> n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> . This contrasts with the case of tree-like resolution where the embedded pigeonhole principle falls into the "non-FPT" category of our dichotomy.
Cited by 22Open access
Eli Ben-Sasson · 2008
Cited by 0
Leroy Chew · White Rose eTheses Online (University of Leeds, The University of Sheffield, University of York) · 2017
Quantified Boolean Formulas (QBF) and their proof complexity are not as well understood as \npropositional formulas, yet remain an area of interest due to their relation to QBF solving. Proof \nsystems for QBF provide a theoretical underpinning for the performance of these solvers. We define \na novel calculus IR-calc, which enables unification of the principal existing resolution-based QBF \ncalculi and applies to the more powerful Dependency QBF (DQBF). \nWe completely reveal the relative power of important QBF resolution systems, settling in \nparticular the relationship between the two different types of resolution-based QBF calculi. The \nmost challenging part of this comparison is to exhibit hard formulas that underlie the exponential \nseparations of the proof systems. In contrast to classical proof complexity we are currently short \nof lower bound techniques for QBF proof systems. To this end we exhibit a new proof technique \nfor showing lower bounds in QBF proof systems based on strategy extraction. We also find that \nthe classical lower bound techniques of the prover-delayer game and feasible interpolation can be \nlifted to a QBF setting and provide new lower bounds. \nWe investigate more powerful proof systems such as extended resolution and Frege systems. We \ndefine and investigate new QBF proof systems that mix propositional rules with a reduction rule, \nwe find the strategy extraction technique also works and directly lifts lower bounds from circuit \ncomplexity. Such a direct transfer from circuit to proof complexity lower bounds has often been \npostulated, but had not been formally established for propositional proof systems prior to this work. \nThis leads to strong lower bounds for restricted versions of QBF Frege, in particular an exponential \nlower bound for QBF Frege systems operating with AC0[p] circuits. In contrast, any non-trivial \nlower bound for propositional AC0[p]-Frege constitutes a major open problem. \n
Cited by 2Open access
Arnold Beckmann · Journal of Logic and Computation · 2005
We define the notion of the uniform reduct of a propositional proof system as the set of those bounded formulas in the language of Peano Arithmetic which have polynomial size proofs under the Paris-Wilkie-translation. With respect to the arithmetic complexity of uniform reducts, we show that uniform reducts are Π10-hard and obviously in Σ20. We also show under certain regularity conditions that each uniform reduct is closed under bounded generalisation; that in the case the language includes a symbol for exponentiation, a uniform reduct is closed under modus ponens if and only if it already contains all true bounded formulas; and that each uniform reduct contains all true Π1b(α)-formulas.
Cited by 1
An Introduction · 2008
Cited by 0
Avi Wigderson · Princeton University Press eBooks · 2019
Cited by 0
Lecturer Paul Beame · 2008
Cited by 0
(:unkn) unknown · TIB Repositorium · 2024
Proof complexity is a multi-disciplinary research area that addresses questions of the general form “how difficult is it to prove certain mathematical facts?” The current workshop focussed on recent advances in our understanding that the analysis of an appropriately tailored concept of “proof” underlies many of the arguments in algorithms, geometry or combinatorics research that make the core of modern theoretical computer science. These include the analysis of practical Boolean satisfiability (SAT) solving algorithms, the size of linear or semidefinite programming formulations of combinatorial optimization problems, the complexity of solving total NP search problems by local methods, and the complexity of describing winning strategies in two-player round-based games, to name just a few important examples.
Cited by 0Open access
Albert Atserias, Meena Mahajan, Jakob Nordström et al. · Oberwolfach Reports · 2024
Proof complexity is a multi-disciplinary research area that addresses questions of the general form “how difficult is it to prove certain mathematical facts?” The current workshop focussed on recent advances in our understanding that the analysis of an appropriately tailored concept of “proof” underlies many of the arguments in algorithms, geometry or combinatorics research that make the core of modern theoretical computer science. These include the analysis of practical Boolean satisfiability (SAT) solving algorithms, the size of linear or semidefinite programming formulations of combinatorial optimization problems, the complexity of solving total NP search problems by local methods, and the complexity of describing winning strategies in two-player round-based games, to name just a few important examples.
Cited by 0Open access
Carlo Cellucci · Synthese · 1985
Cited by 11
Eli Ben-Sasson · 2001
In this thesis we explore several well-known proof systems for co-SAT - the language of unsatisfiable Boolean circuits. We prove lower bounds for important complexity measures, such as proof size, and proof space. Our main contribution is presenting quite general, and very natural, combinatorial conditions on the input circuit, that ensure high proof complexity. More explicitly, we propose the following paradigm: If C is an unsatisfiable circuit that is a conjunction of Boolean constraints, and 1. C is expanding, i.e. every small subset of the constraints has many variables. 2. Each
Cited by 0
Ryan O’Donnell, Yuan Zhou · 2013
This work is concerned with the proof-complexity of certifying that optimization problems do not have good solutions. Specifically we consider bounded-degree “Sum of Squares” (SOS) proofs, a powerful algebraic proof system introduced in 1999 by Grigoriev and Vorobjov. Work of Shor, Lasserre, and Parrilo shows that this proof is automatizable using semidefinite programming (SDP), meaning that any n-variable degree-d proof can be found in time nO(d). Furthermore, the SDP is dual to the well-known Lasserre SDP hierarchy, meaning that the “d/2-round Lasserre value” of an optimization problem is equal to the best bound provable using a degree-d SOS proof. These ideas were exploited in a recent paper by Barak et al. (STOC 2012) which shows that the known “hard instances” for the Unique-Games problem are in fact optimally solved by a constant level of the Lasserre SDP hierarchy. We continue the study of the power of SOS proofs in the context of difficult optimization problems. In particular, we show that the Balanced-Separator integrality gap instances proposed by Devanur et al. can have their optimal value certified by a degree-4 SOS proof. The key ingredient is an SOS proof of the KKL Theorem. We also investigate the extent to which the Khot–Vishnoi Max-Cut integrality gap instances can have their optimum value certified by an SOS proof. We show they can be certified to within a factor .952 (> .878) using a constant-degree proof. These investigations also raise an interesting mathematical question: is there a constant-degree SOS proof of the Central Limit Theorem?
Cited by 33
(:unkn) unknown · TIB Repositorium · 2017
Proof complexity is a multi-disciplinary intellectual endeavor that addresses questions of the general form “how difficult is it to prove certain mathematical facts?” The current workshop focused on recent advances in our understanding of logic-based proof systems and on connections to algorithms, geometry and combinatorics research, such as the analysis of approximation algorithms, or the size of linear or semidefinite programming formulations of combinatorial optimization problems, to name just two important examples.
Cited by 0Open access