Short propositional refutations for dense random 3CNF formulas
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 1689045 (Why is no real title available?)
- scientific article; zbMATH DE number 5899254 (Why is no real title available?)
- scientific article; zbMATH DE number 4059391 (Why is no real title available?)
- scientific article; zbMATH DE number 3583767 (Why is no real title available?)
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 1559592 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- scientific article; zbMATH DE number 227056 (Why is no real title available?)
- scientific article; zbMATH DE number 2196512 (Why is no real title available?)
- A Computing Procedure for Quantification Theory
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- A machine program for theorem-proving
- Cutting planes, connectivity, and threshold logic
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Logical foundations of proof complexity
- Lower bounds for k-DNF resolution on random 3-CNFs
- Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
- Lower bounds to the size of constant-depth propositional proofs
- Many hard examples for resolution
- Matrix Analysis
- Notes on polynomially bounded arithmetic
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
- On Interpolation and Automatization for Frege Systems
- On the weak pigeonhole principle
- Optimality of size-degree tradeoffs for polynomial calculus
- Proving Infinitude of Prime Numbers Using Binomial Coefficients
- Random CNF's are hard for the polynomial calculus
- Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
- Recognizing more random unsatisfiable 3-SAT instances efficiently
- Resolution Is Not Automatizable Unless W[P] Is Tractable
- Short proofs are narrow—resolution made simple
- Short proofs for the determinant identities
- Short propositional refutations for dense random 3CNF formulas
- Sparser random 3-SAT refutation algorithms and the interpolation problem (extended abstract)
- The efficiency of resolution and Davis-Putnam procedures
- The intractability of resolution
- The proof complexity of linear algebra
- The relative efficiency of propositional proof systems
- Theories for TC0 and Other Small Complexity Classes
Cited in
(10)- Refuting random 3CNF formulas in propositional logic
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- Some 3CNF properties are hard to test
- scientific article; zbMATH DE number 5899254 (Why is no real title available?)
- 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)
