Problemy z wydajnym rozwiązaniem, z wyjątkiem niewielkiej części nakładów

Problemem zatrzymania maszyn Turinga jest być może kanoniczny nierozstrzygalny zestaw. Niemniej jednak dowodzimy, że istnieje algorytm decydujący o prawie wszystkich jego wystąpieniach. Problem zatrzymania należy zatem do rosnącej liczby osób wykazujących zjawisko teorii złożoności „czarnej dziury”, w którym trudność niewykonalnego lub nierozstrzygalnego problemu ogranicza się do bardzo małego regionu, czarnej dziury, na zewnątrz którego problem jest łatwo.

[Joel David Hamkins i Alexei Miasnikov, „ Problem zatrzymania można rozstrzygnąć na podstawie prawdopodobieństwa asymptotycznego ”, 2005]

Czy ktoś może podać odniesienia do innych „czarnych dziur” w teorii złożoności lub do innego miejsca, w którym omawiane są te lub powiązane pojęcia?

— Jim Graber
źródło

Joel regularnie odwiedza MathOverflow, możesz tutaj zadać pytanie, aby uzyskać od niego odpowiedź. IIRC pojawiło się pytanie o wynik.

— Kaveh

Zobacz także HeurP .

— Kaveh

Być może innym przykładem jest Graph Isomorphism (który jest problemem pośrednim NP). Na „rzeczywistych instancjach” jest to bardzo łatwe (banalne dla przypadkowych instancji?), A dla wielu klas grafów istnieje algorytm wielomianowy. „Czarna dziura” wydaje się tak ciasna, że generowanie twardych instancji nie jest tak łatwe, a nauty, jedno z najbardziej wydajnych narzędzi do jej rozwiązywania , jest często używane do generowania (twardych) instancji. Ale być może „czarna dziura” zniknie i pozostawi biedny OG w P :-D

— Marzio De Biasi

@Marzio, przykłady ze świata nierzeczywistego zwykle nie stanowią niewielkiej części wszystkich instancji i różnią się od tego, o czym mówią w artykule.

— Kaveh

HeurP brzmi tak, jakby zakładał rozkład prawdopodobieństwa na instancje, ale myślę, że całkiem inna formalizacja tego zjawiska byłaby następująca: Język

jest trudny dla niektórych klas, ale istnieje problem z obietnicą

jest to w pewnej łatwiejszej klasie z

„asymptotycznie gęstym” w

, gdzie asmyptotycznie jest to, że rozmiar łańcuchów w językach dochodzi do nieskończoności.

A

$A$

A^{'} = (A_{y}^{'}, A_{n}^{'})

$A' = (A'_y,A'_n)$

A_{y}^{'}

$A'_y$

A

$A$

A_{n}^{'}

$A'_n$

\bar{A}

$\bar{A}$

— usul

Odpowiedzi:

Nie jestem pewien, czy tego właśnie szukasz, ale przejście fazowe w losowej SAT jest przykładem. Niech będzie stosunkiem liczby zdań do liczby zmiennych. Wówczas losowa instancja SAT z parametrem najprawdopodobniej będzie zadowalająca, jeśli jest mniejsza niż stała stała (blisko 4,2) i jest bardzo prawdopodobne, że będzie niezadowalająca, jeśli jest nieco większa niż ta stała. „Czarna dziura” to przejście fazowe. $\rho$ $\rho$ $\rho$ $\rho$

— Suresh Venkat
źródło

Podobnie do tego, cykl Ham można wykazać, że można go rozwiązać w czasie rzeczywistym na losowym grafie (zgodnie z pewnym rozsądnym procesem generowania losowego), ale jest on trudny do NP tylko ze względu na bardzo specjalnie skonstruowane przykłady. Istnieje wiele innych przykładów wzdłuż tej linii.

— JimN

Podobnie jak problem zatrzymania, problem korespondencji posta jest ogólnie nierozstrzygalny. Praca magisterska Linga Zhao opisuje duży zestaw możliwych do rozwiązania przypadków PCP, w tym niektóre „twarde” przypadki. Ale nie wiem, czy rozmiar / gęstość / miara jego zestawu możliwych do rozwiązania instancji jest na równi z cytowanym przez ciebie rezultatem problemu zatrzymania.

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

— JimN
źródło