The Complexity of Propositional Proofs (Q5444711): Difference between revisions

@@ Property / DOI @@
-.2178/bsl/1203350879
@@ Property / DOI: 10.2178/bsl/1203350879 / rank @@
-Normal rank
@@ Property / cites work @@
+On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
+Normal rank
@@ Property / cites work @@
+Q4662832
@@ Property / cites work: Q4662832 / rank @@
+Normal rank
@@ Property / cites work @@
+On Interpolation and Automatization for Frege Systems
+Normal rank
@@ Property / cites work @@
+Lower bounds for cutting planes proofs with small coefficients
+Normal rank
@@ Property / cites work @@
+Short proofs are narrow—resolution made simple
@@ Property / cites work: Short proofs are narrow—resolution made simple / rank @@
+Normal rank
@@ Property / cites work @@
+Near optimal seperation of tree-like and general resolution
+Normal rank
@@ Property / cites work @@
+The Efficiency of Resolution and Davis--Putnam Procedures
+Normal rank
@@ Property / cites work @@
+Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
+Normal rank
@@ Property / cites work @@
+On the automatizability of resolution and related propositional proof systems
+Normal rank
@@ Property / cites work @@
+Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms
+Normal rank
@@ Property / cites work @@
+Space Complexity in Propositional Calculus
@@ Property / cites work: Space Complexity in Propositional Calculus / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of the pigeonhole principle
@@ Property / cites work: The complexity of the pigeonhole principle / rank @@
+Normal rank
@@ Property / cites work @@
+Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis
+Normal rank
@@ Property / cites work @@
+The proof complexity of linear algebra
@@ Property / cites work: The proof complexity of linear algebra / rank @@
+Normal rank
@@ Property / cites work @@
+A Switching Lemma for Small Restrictions and Lower Bounds for <i>k</i>-DNF Resolution
+Normal rank
@@ Property / cites work @@
+Exponential separation between Res(\(k\)) and Res(\(k+1\)) for \(k \leqslant \varepsilon\log n\)
+Normal rank
@@ Property / cites work @@
+Q4220572
@@ Property / cites work: Q4220572 / rank @@
+Normal rank
@@ Property / cites work @@
+Provability of the pigeonhole principle and the existence of infinitely many primes
+Normal rank
@@ Property / cites work @@
+Existence and feasibility in arithmetic
@@ Property / cites work: Existence and feasibility in arithmetic / rank @@
+Normal rank
@@ Property / cites work @@
+A lower bound for the complexity of Craig's interpolants in sentential logic
+Normal rank
@@ Property / cites work @@
+Resolution cannot polynomially simulate compressed-BFS
+Normal rank
@@ Property / cites work @@
+The intractability of resolution
@@ Property / cites work: The intractability of resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Hiding propositional constants in BDDs.
@@ Property / cites work: Hiding propositional constants in BDDs. / rank @@
+Normal rank
@@ Property / cites work @@
+Outline of an algorithm for integer solutions to linear programs
+Normal rank
@@ Property / cites work @@
+Sharp thresholds of graph properties, and the $k$-sat problem
+Normal rank
@@ Property / cites work @@
+\(\text{Count}(q)\) does not imply \(\text{Count}(p)\)
+Normal rank
@@ Property / cites work @@
+Resolution lower bounds for perfect matching principles
+Normal rank
@@ Property / cites work @@
+Lower bounds for the polynomial calculus
@@ Property / cites work: Lower bounds for the polynomial calculus / rank @@
+Normal rank
@@ Property / cites work @@
+Resolution lower bounds for the weak pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Linear-size constant-depth polylog-threshold circuits
+Normal rank
@@ Property / cites work @@
+Q5286672
@@ Property / cites work: Q5286672 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for resolution and cutting plane proofs and monotone computations
+Normal rank
@@ Property / cites work @@
+Lower bounds to the size of constant-depth propositional proofs
+Normal rank
@@ Property / cites work @@
+Exponential lower bounds for the pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Optimal proof systems imply complete sets for promise classes
+Normal rank
@@ Property / cites work @@
+Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations
+Normal rank
@@ Property / cites work @@
+Lower bounds for the polynomial calculus and the Gröbner basis algorithm
+Normal rank
@@ Property / cites work @@
+Expander graphs and their applications
@@ Property / cites work: Expander graphs and their applications / rank @@
+Normal rank
@@ Property / cites work @@
+A machine program for theorem-proving
@@ Property / cites work: A machine program for theorem-proving / rank @@
+Normal rank
@@ Property / cites work @@
+Space bounds for resolution
@@ Property / cites work: Space bounds for resolution / rank @@
+Normal rank
@@ Property / cites work @@
+A new proof of the weak pigeonhole principle
@@ Property / cites work: A new proof of the weak pigeonhole principle / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of resolution with bounded conjunctions
+Normal rank
@@ Property / cites work @@
+An accurate and scalable collaborative recommender
+Normal rank
@@ Property / cites work @@
+A Computing Procedure for Quantification Theory
@@ Property / cites work: A Computing Procedure for Quantification Theory / rank @@
+Normal rank
@@ Property / cites work @@
+Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs
+Normal rank
@@ Property / cites work @@
+Q4856172
@@ Property / cites work: Q4856172 / rank @@
+Normal rank
@@ Property / cites work @@
+An overview of backtrack search satisfiability algorithms
+Normal rank
@@ Property / cites work @@
+Cones of Matrices and Set-Functions and 0–1 Optimization
+Normal rank
@@ Property / cites work @@
+An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Some consequences of cryptographical conjectures for \(S_2^1\) and EF
+Normal rank
@@ Property / cites work @@
+Propositional proof systems, the consistency of first order theories and the complexity of computations
+Normal rank
@@ Property / cites work @@
+On the weak pigeonhole principle
@@ Property / cites work: On the weak pigeonhole principle / rank @@
+Normal rank
@@ Property / cites work @@
+Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+Many hard examples for resolution
@@ Property / cites work: Many hard examples for resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Edmonds polytopes and a hierarchy of combinatorial problems. (Reprint)
+Normal rank
@@ Property / cites work @@
+Good degree bounds on Nullstellensatz refutations of the induction principle
+Normal rank
@@ Property / cites work @@
+Q4365127
@@ Property / cites work: Q4365127 / rank @@
+Normal rank
@@ Property / cites work @@
+Linear gaps between degrees for the polynomial calculus modulo distinct primes
+Normal rank
@@ Property / cites work @@
+Bounded arithmetic, proof complexity and two papers of Parikh
+Normal rank
@@ Property / cites work @@
+Propositional consistency proofs
@@ Property / cites work: Propositional consistency proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial size proofs of the propositional pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Q3794177
@@ Property / cites work: Q3794177 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002766
@@ Property / cites work: Q3002766 / rank @@
+Normal rank
@@ Property / cites work @@
+Homogenization and the polynomial calculus
@@ Property / cites work: Homogenization and the polynomial calculus / rank @@
+Normal rank
@@ Property / DOI @@
+.2178/BSL/1203350879
@@ Property / DOI: 10.2178/BSL/1203350879 / rank @@
+Normal rank