Short Proofs Are Hard to Find (Q5091243): Difference between revisions

@@ label / en / label / en @@
+Short Proofs Are Hard to Find
@@ Property / DOI @@
-.4230/LIPIcs.ICALP.2019.84
@@ Property / DOI: 10.4230/LIPIcs.ICALP.2019.84 / rank @@
-Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Minimum propositional proof length is NP-hard to linearly approximate
+Normal rank
@@ Property / cites work @@
+Resolution Is Not Automatizable Unless W[P] Is Tractable
+Normal rank
@@ Property / cites work @@
+Simple Constructions of Almost k-wise Independent Random Variables
+Normal rank
@@ Property / cites work @@
+A combinatorial characterization of resolution width
+Normal rank
@@ Property / cites work @@
+Narrow Proofs May Be Maximally Long
@@ Property / cites work: Narrow Proofs May Be Maximally Long / rank @@
+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 @@
+Non-automatizability of bounded-depth Frege proofs
+Normal rank
@@ Property / cites work @@
+On Interpolation and Automatization for Frege Systems
+Normal rank
@@ Property / cites work @@
+Polybori: A framework for Gröbner-basis computations with Boolean polynomials
+Normal rank
@@ Property / cites work @@
+Q4228469
@@ Property / cites work: Q4228469 / 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 @@
+A Computing Procedure for Quantification Theory
@@ Property / cites work: A Computing Procedure for Quantification Theory / rank @@
+Normal rank
@@ Property / cites work @@
+On the automatizability of polynomial calculus
@@ Property / cites work: On the automatizability of polynomial calculus / rank @@
+Normal rank
@@ Property / cites work @@
+Monotone circuit lower bounds from resolution
@@ Property / cites work: Monotone circuit lower bounds from resolution / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of \(k\)-SAT
@@ Property / cites work: On the complexity of \(k\)-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+Some consequences of cryptographical conjectures for \(S_2^1\) and EF
+Normal rank
@@ Property / cites work @@
+Global Optimization with Polynomials and the Problem of Moments
+Normal rank
@@ Property / cites work @@
+Q5111409
@@ Property / cites work: Q5111409 / rank @@
+Normal rank
@@ Property / cites work @@
+Cutting planes in integer and mixed integer programming
+Normal rank
@@ Property / cites work @@
+GRASP: a search algorithm for propositional satisfiability
+Normal rank
@@ Property / cites work @@
+Small-Bias Probability Spaces: Efficient Constructions and Applications
+Normal rank
@@ Property / cites work @@
+On the power of clause-learning SAT solvers as resolution engines
+Normal rank
@@ Property / cites work @@
+Proofs as Games
@@ Property / cites work: Proofs as Games / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549708
@@ Property / cites work: Q3549708 / 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 @@
+A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
+Normal rank
@@ Property / full work available at URL @@
+https://drops.dagstuhl.de/opus/volltexte/2019/10660/pdf/LIPIcs-ICALP-2019-84.pdf
+Normal rank
@@ Property / OpenAlex ID @@
+W2969433745
@@ Property / OpenAlex ID: W2969433745 / rank @@
+Normal rank
@@ Property / title @@
+Short Proofs Are Hard to Find (English)
@@ Property / title: Short Proofs Are Hard to Find (English) / rank @@
+Normal rank
@@ Property / DOI @@
+.4230/LIPICS.ICALP.2019.84
@@ Property / DOI: 10.4230/LIPICS.ICALP.2019.84 / rank @@
+Normal rank