scientific article; zbMATH DE number 1775444
From MaRDI portal
Publication:4542576
zbMATH Open1028.68067MaRDI QIDQ4542576FDOQ4542576
Authors: Toniann Pitassi, Paul Beame, Richard Karp, Michael Saks 
Publication date: 1 August 2002
Title of this publication is not available (Why is that?)
Recommendations
Cited In (35)
- Title not available (Why is that?)
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- Refuting random 3CNF formulas in propositional logic
- 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
- Unsatisfiable linear CNF formulas are large and complex
- An efficient local search method for random 3-satisfiability
- Space proof complexity for random 3-CNFs
- Title not available (Why is that?)
- Lower bounds for \(k\)-DNF resolution on random 3-CNFs
- A sharp threshold in proof complexity
- An Introduction to Lower Bounds on Resolution Proof Systems
- An improved generator for 3-CNF formulas
- Short propositional refutations for dense random 3CNF formulas
- Short propositional refutations for dense random 3CNF formulas
- On ε‐biased generators in NC0
- Exponential lower bounds for DPLL algorithms on satisfiable random 3-CNF formulas
- 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 smoothed \(k\)-CNF formulas and the \texttt{Walksat} algorithm
- On unique satisfiability and the threshold behavior of randomized reductions
- A sharp threshold in proof complexity yields lower bounds for satisfiability search
- On sufficient conditions for unsatisfiability of random formulas
- Random resolution refutations
- 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)
