2016 · 42 citations · 22 references
Natural SciencesComputer ScienceMathematicsLogicSet TheoryTheory Of ComputationAxiomatic Set TheoryBoolean AlgebraBoolean OperationsMathematical LogicPredicate LogicBoolean SatisfiabilityExtended FregeFrege SystemsLower Bounds
Recently Beyersdorff, Bonacina, and Chew [10] introduced a natural class of Frege systems for quantified Boolean formulas (QBF) and showed strong lower bounds for restricted versions of these systems. Here we provide a comprehensive analysis of the new extended Frege system from [10], denoted EF + ∀red, which is a natural extension of classical extended Frege EF.
22
The relative efficiency of propositional proof systems
Stephen Cook, Robert A. Reckhow · Journal of Symbolic Logic · 1979 · 827 citations
Existence and feasibility in arithmetic
Rohit Parikh · Journal of Symbolic Logic · 1971 · 331 citations