black hole problem
Miasnikov's concept in decision/complexity theory of a problem that is hard overall but whose difficulty is concentrated in a tiny region, outside of which it is easy to solve.
As defined in 282 | Joel David Hamkins on Puzzles of Reality and Infinity
Where it comes up · 1
Most important claims · 1 of 1Search all claims for “black hole problem” →
- Hamkins and Miasnikov proved that although the halting problem is undecidable, for the one-way infinite tape Turing machine model it is decidable on a set of probability one: as program size grows, the proportion of programs whose halting status can be decided approaches 100%, because by Polya's recurrence theorem a random-walking head falls off the tape with probability one, though the result is fragile because it depends on the chosen computational model.282 | Joel David Hamkins on Puzzles of Reality and Infinity