scientific article; zbMATH DE number 1775444
From MaRDI portal
Publication:4542576
zbMATH Open1028.68067MaRDI QIDQ4542576FDOQ4542576
Michael Saks, Paul Beame, Richard Karp, Toniann Pitassi
Publication date: 1 August 2002
Title of this publication is not available (Why is that?)
Recommendations
Cited In (24)
- Title not available (Why is that?)
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- Typical case complexity of satisfiability algorithms and the threshold phenomenon
- A perspective on certain polynomial-time solvable classes of satisfiability
- On the limit of branching rules for hard random unsatisfiable 3-SAT
- Random CNF's are hard for the polynomial calculus
- An efficient local search method for random 3-satisfiability
- Title not available (Why is that?)
- An Introduction to Lower Bounds on Resolution Proof Systems
- An improved generator for 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
- Space complexity of random formulae in resolution
- An Upper Bound on the Space Complexity of Random Formulae in Resolution
- Many hard examples in exact phase transitions
- Many hard examples for 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)
