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?

cc.complexity-theory reference-request computability undecidability 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