scientific article; zbMATH DE number 1775444

zbMath1028.68067MaRDI QIDQ4542576

Toniann Pitassi, Michael E. Saks, P. W. Beame, Richard M. Karp

Publication date: 1 August 2002

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

unsatisfiabilityrandom \(k\)-CNF formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (13)

An improved generator for 3-CNF formulas ⋮ Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes ⋮ Many hard examples in exact phase transitions ⋮ A sharp threshold in proof complexity yields lower bounds for satisfiability search ⋮ On the limit of branching rules for hard random unsatisfiable 3-SAT ⋮ An Introduction to Lower Bounds on Resolution Proof Systems ⋮ The complexity of properly learning simple concept classes ⋮ An Upper Bound on the Space Complexity of Random Formulae in Resolution ⋮ 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 ⋮ On ε‐biased generators in NC⁰ ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon ⋮ An efficient local search method for random 3-satisfiability ⋮ A perspective on certain polynomial-time solvable classes of satisfiability

This page was built for publication: