## CSDM: A Tutorial on the Likely Worst-Case Complexities of NP-Complete Problems

The P vs. NP problem has sometimes been unofficially paraphrased as asking whether

it is possible to improve on exhaustive search for such problems as Satisfiability, Clique,

Graph Coloring, etc. However, known algorithms for each of these problems indeed are

substantially better than exhaustive search, if still exponential. Furthermore, although a

polynomial-time algorithm for any one of these problems implies one for all of them, these

improved exponential algorithms are highly specific, and it is unclear what the limit of

improvement should be.