scientific article; zbMATH DE number 1775444
From MaRDI portal
Publication:4542576
Recommendations
Cited in
(35)- Many hard examples for resolution
- scientific article; zbMATH DE number 408796 (Why is no real title available?)
- Refuting random 3CNF formulas in propositional logic
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- Typical case complexity of satisfiability algorithms and the threshold phenomenon
- Random CNF's are hard for the polynomial calculus
- A perspective on certain polynomial-time solvable classes of satisfiability
- On the limit of branching rules for hard random unsatisfiable 3-SAT
- Unsatisfiable linear CNF formulas are large and complex
- Space proof complexity for random 3-CNFs
- An efficient local search method for random 3-satisfiability
- scientific article; zbMATH DE number 5899254 (Why is no real title available?)
- Lower bounds for k-DNF resolution on random 3-CNFs
- An improved generator for 3-CNF formulas
- A sharp threshold in proof complexity
- An Introduction to Lower Bounds on Resolution Proof Systems
- Short propositional refutations for dense random 3CNF formulas
- Short propositional refutations for dense random 3CNF formulas
- Exponential lower bounds for DPLL algorithms on satisfiable random 3-CNF formulas
- On ε‐biased generators in NC0
- Automata, Languages and Programming
- Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT
- The resolution complexity of random graph \(k\)-colorability
- Strong Refutation Heuristics for Random k-SAT
- The structure of the set of satisfying assignments for a random \(k\)-CNF
- The complexity of properly learning simple concept classes
- The efficiency of resolution and Davis-Putnam procedures
- On unique satisfiability and the threshold behavior of randomized reductions
- A sharp threshold in proof complexity yields lower bounds for satisfiability search
- On smoothed \(k\)-CNF formulas and the \texttt{Walksat} algorithm
- On sufficient conditions for unsatisfiability of random formulas
- Random resolution refutations
- Many hard examples in exact phase transitions
- Space complexity of random formulae in resolution
- An Upper Bound on the Space Complexity of Random Formulae in Resolution
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4542576)
