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