# Problems with efficient solution except for a small fraction of inputs

The halting problem for Turing machines is perhaps the canonical undecidable set. Nevertheless, we prove that there is an algorithm deciding almost all instances of it. The halting problem is therefore among the growing collection of those exhibiting the “black hole” phenomenon of complexity theory, by which the difficulty of an unfeasible or undecidable problem is confined to a very small region, a black hole, outside of which the problem is easy.

[Joel David Hamkins and Alexei Miasnikov, "The halting problem is decidable on a set of asymptotic probability one", 2005]

Can anyone provide references to other “black holes” in complexity theory, or another place where this or related concepts are discussed?

• Joel regularly visits MathOverflow, you can ask the question here to get an answer from him. IIRC there was a question about the result there. – Kaveh Mar 13 '14 at 21:54
• HeurP sounds like it assumes a probability distribution on instances, but I think a nice different formalization of the phenomenon would be this: The language $A$ is hard for some class, but there exists a promise problem $A' = (A'_y,A'_n)$ that is in some easier class with $A'_y$ "asmyptotically dense" in $A$ and $A'_n$ "asymptotically dense" in $\bar{A}$, where asmyptotically is as the size of the strings in the languages goes to infinity. – usul Mar 14 '14 at 1:37
I'm not sure whether this is what you're looking, but the phase transition in random SAT is an example. Let $\rho$ be the ratio of number of clauses to number of variables. Then a random SAT instance with parameter $\rho$ is very likely to be satisfiable if $\rho$ is less than a fixed constant (near 4.2) and is very likely to be unsatisfiable if $\rho$ is a little bit more than this constant. The "black hole" is the phase transition.