Short propositional refutations for dense random 3CNF formulas
DOI10.1016/J.APAL.2014.08.001zbMATH Open1391.03042OpenAlexW2950542447MaRDI QIDQ741088FDOQ741088
Authors: D. Kharzeev 
Publication date: 10 September 2014
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.apal.2014.08.001
Recommendations
Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Matrix Analysis
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Theories for TC0 and Other Small Complexity Classes
- Notes on polynomially bounded arithmetic
- Logical foundations of proof complexity
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- The relative efficiency of propositional proof systems
- Many hard examples for resolution
- Short proofs are narrow—resolution made simple
- The intractability of resolution
- Title not available (Why is that?)
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
- On the weak pigeonhole principle
- Resolution Is Not Automatizable Unless W[P] Is Tractable
- Lower bounds to the size of constant-depth propositional proofs
- On Interpolation and Automatization for Frege Systems
- Random CNF's are hard for the polynomial calculus
- Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
- The efficiency of resolution and Davis-Putnam procedures
- Title not available (Why is that?)
- Lower bounds for k-DNF resolution on random 3-CNFs
- The proof complexity of linear algebra
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
- Title not available (Why is that?)
- Recognizing more random unsatisfiable 3-SAT instances efficiently
- Cutting planes, connectivity, and threshold logic
- Title not available (Why is that?)
- Optimality of size-degree tradeoffs for polynomial calculus
- Short propositional refutations for dense random 3CNF formulas
- Proving Infinitude of Prime Numbers Using Binomial Coefficients
- Title not available (Why is that?)
- Sparser random 3-SAT refutation algorithms and the interpolation problem (extended abstract)
- Short proofs for the determinant identities
Cited In (10)
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- Refuting random 3CNF formulas in propositional logic
- Some 3CNF properties are hard to test
- Title not available (Why is that?)
- Lower bounds for \(k\)-DNF resolution on random 3-CNFs
- Short propositional refutations for dense random 3CNF formulas
- INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH
- First-order reasoning and efficient semi-algebraic proofs
- Sparser random 3-SAT refutation algorithms and the interpolation problem (extended abstract)
- On sufficient conditions for unsatisfiability of random formulas
This page was built for publication: Short propositional refutations for dense random 3CNF formulas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q741088)
