Проблема остановки для машин Тьюринга, возможно, является каноническим неразрешимым множеством. Тем не менее, мы доказываем, что существует алгоритм, решающий почти все его экземпляры. Таким образом, проблема остановки является одной из растущих коллекций тех, кто демонстрирует феномен «черной дыры» теории сложности, с помощью которого трудность невыполнимой или неразрешимой проблемы ограничивается очень маленькой областью, черной дырой, за пределами которой проблема легко.
[Джоэл Дэвид Хэмкинс и Алексей Мясников, « Проблема остановки разрешима на множестве асимптотической вероятности один », 2005]
Может ли кто-нибудь дать ссылки на другие «черные дыры» в теории сложности или другое место, где обсуждаются эти или связанные понятия?
Ответы:
Я не уверен, что это то, что вы ищете, но фазовый переход в случайном SAT является примером. Пусть - отношение количества предложений к числу переменных. Тогда случайный экземпляр SAT с параметром ρ вполне вероятно будет выполнимым, если ρρ ρ ρ меньше , чем фиксированная константа (около 4,2) и очень вероятно, будет невыполнима , если немного больше , чем эта константа. «Черная дыра» - это фазовый переход.ρ
источник
Как и проблема с остановкой, проблема с перепиской вообще неразрешима. Магистерская работа Лин Чжао описывает большой набор разрешимых примеров проблемы PCP, включая некоторые «трудные» случаи. Но я не знаю, соответствует ли размер / плотность / мера его множества разрешимых экземпляров тому результату проблемы остановки, который вы цитируете.
http://webdocs.cs.ualberta.ca/~games/PCP/paper/CG2002.pdf
источник