There exist problems for which the most efficient known decision algorithm has exponential time complexity in the worst case (and in fact are known to be \(\textbf{NP}\)-hard in the general case – see Section 3.2)  but which operate in polynomial time either in the average case or for a large subclass of problem instances of practical interest. Commonly cited examples include \(\sc{SAT}\) (e.g. Cook and Mitchell 1997), as well as some problems from graph theory (e.g. Scott and Sorkin 2006), and computational algebra (e.g. Kapovich et al. 2003).