A probabilistic algorithm for k-SAT and constraint satisfaction problems

DOI10.1109/SFFCS.1999.814612MaRDI QIDQ7238305zbMATH OpenFDO

Authors T. Schoning

Publication date 6 May 2026

Full work available at URL https://doi.org/10.1109/SFFCS.1999.814612

Mathematics Subject Classification ID

Graph theory (05Cxx) Data structures (68P05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Formal languages and automata (68Q45) Discrete mathematics in relation to computer science (68Rxx) Nonnumerical algorithms (68W05) Quantum computation (81P68)

Cited in

(2)

• Breaking the 2ⁿ barrier for 5-coloring and 6-coloring
• Faster exponential algorithms for cut problems via geometric data structures

This page was built for publication: A probabilistic algorithm for \(k\)-SAT and constraint satisfaction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7238305)