<p>Like the Halting problem, <i>Post's Correspondence Problem</i> is undecidable in general. Ling Zhao's Master's thesis describes a large set of solvable instances of the PCP problem, including some "hard" instances. But I don't know if the size/density/measure of his set of solvable instances is on par with the Halting Problem result you cite.</p>

<p><a href="http://webdocs.cs.ualberta.ca/~games/PCP/paper/CG2002.pdf">http://webdocs.cs.ualberta.ca/~games/PCP/paper/CG2002.pdf</a></p>

CC BY-SA 3.0
2014-03-14T01:05:55.743Z
2014-03-14T01:05:55.743Z
JimN
<p>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. </p>

CC BY-SA 3.0
2014-03-14T00:52:25.530Z
Similar to this, Ham Cycle can be shown to be polytime solvable on a random graph (according to some reasonable random generation process), yet it is NP-hard just because of very specially-constructed examples. There are many other examples along this line.
JimN
CC BY-SA 3.0
2014-03-13T21:31:26.053Z
2014-03-13T21:31:26.053Z
Suresh Venkat
<blockquote>
  <p>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.  </p>
  
  <p>[Joel David Hamkins and Alexei Miasnikov, "<a href="http://arxiv.org/abs/math/0504351">The halting problem is decidable on a set of asymptotic probability one</a>", 2005]</p>
</blockquote>

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

CC BY-SA 3.0
2014-03-13T21:54:38.750Z
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
CC BY-SA 3.0
2014-03-13T21:59:38.397Z
See also [HeurP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:H#heurp).
Kaveh
CC BY-SA 3.0
2014-03-13T23:42:50.667Z
Perhaps another example is Graph Isomorphism (which is an NP-intermediate problem).
On "real instances" it is very easy (trivial for random instances?) and for many graph classes there is a polynomial time algorithm. The "black hole" seems so tight that it is not so easy to generate hard instances and nauty, one of the most efficient tool to *solve* it, is often used to *generate* (hard) instances. But perhaps, the "black hole" will vanish and will leave the poor GI in P :-D
Marzio De Biasi
CC BY-SA 3.0
2014-03-14T01:33:50.897Z
@Marzio, non-real world examples are not usually a small fraction of all instances and is different from what they are referring to in the paper.
Kaveh
CC BY-SA 3.0
2014-03-14T01:37:54.053Z
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
<cc.complexity-theory><reference-request><computability><undecidability>
Problems with efficient solution except for a small fraction of inputs
Jim Graber
# Problems with efficient solution except for a small fraction of inputs

(Asked by: username_0 on 2014-03-13)

> 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](http://arxiv.org/abs/math/0504351)", 2005]

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

**Tags:** cc.complexity-theory, reference-request, computability, undecidability

> **Comments:**
> **username_1**: 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.  
> **username_1**: See also [HeurP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:H#heurp).  
> **username_2**: Perhaps another example is Graph Isomorphism (which is an NP-intermediate problem). On "real instances" it is very easy (trivial for random instances?) and for many graph classes there is a polynomial time algorithm. The "black hole" seems so tight that it is not so easy to generate hard instances and nauty, one of the most efficient tool to *solve* it, is often used to *generate* (hard) instances. But perhaps, the "black hole" will vanish and will leave the poor GI in P :-D  
> **username_1**: @Marzio, non-real world examples are not usually a small fraction of all instances and is different from what they are referring to in the paper.  
> **username_3**: 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.  

---

## 2 answers

### Answer by username_5 on 2014-03-13. Score: 15 | Accepted answer

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.

> **Comments:**
> **username_4**: Similar to this, Ham Cycle can be shown to be polytime solvable on a random graph (according to some reasonable random generation process), yet it is NP-hard just because of very specially-constructed examples. There are many other examples along this line.  

---

### Answer by username_4 on 2014-03-14. Score: 5

Like the Halting problem, *Post's Correspondence Problem* is undecidable in general. Ling Zhao's Master's thesis describes a large set of solvable instances of the PCP problem, including some "hard" instances. But I don't know if the size/density/measure of his set of solvable instances is on par with the Halting Problem result you cite.

<http://webdocs.cs.ualberta.ca/~games/PCP/paper/CG2002.pdf>


---

