Problemy decyzyjne w

15

Jakie są przykłady trudnych problemów decyzyjnych, które można rozwiązać w czasie wielomianowym? Szukam problemów, dla których optymalny algorytm jest „wolny” lub problemów, dla których najszybszy znany algorytm jest „wolny”.

Oto dwa przykłady:

Rozpoznawanie idealnych wykresów. W swojej pracy FOCS'03 [1] Cornuéjols, Liu i Vuskovic podali algorytm czasowy dla problemu, gdzie jest liczbą wierzchołków. Nie jestem pewien, czy ta granica została poprawiona, ale jak rozumiem, potrzebny jest przełom, aby uzyskać szybszy algorytm. (Autorzy podają algorytm czasowy w wersji czasopisma [1], patrz tutaj ). $O(n^{10})$ $n$ $O(n^9)$
Rozpoznawanie wykresów map. Thorup [2] podał dość złożony algorytm z wykładnikiem wynoszącym (około?) . Być może zostało to nawet znacznie poprawione, ale nie mam dobrego odniesienia. $120$

Szczególnie interesują mnie problemy o znaczeniu praktycznym, a uzyskanie „szybkiego” (a nawet praktycznego) algorytmu jest otwarte od kilku lat.

[1] Cornuéjols, Gérard, Xinming Liu i Kristina Vuskovic. „Algorytm wielomianowy do rozpoznawania idealnych wykresów”. Podstawy informatyki, 2003. Postępowanie. 44. doroczne sympozjum IEEE w sprawie. IEEE, 2003.

[2] Thorup, Mikkel. „Mapuj wykresy w czasie wielomianowym”. Podstawy informatyki, 1998. Postępowanie. 39. doroczne sympozjum poświęcone. IEEE, 1998.

algorithms complexity-theory reference-request

— Juho
źródło

Możesz rzucić okiem na Raymonda Greenlawa, H. Jamesa Hoovera, Waltera L. Ruzzo, Granice obliczeń równoległych:

Teoria kompletności

P

$\mathsf{P}$ , 1995

— Kaveh

12

Być może następujące przykłady pasują do twoich przykładów:

(Wersja decyzyjna) Kolorowanie, klika, zestaw stabilny, przykrycie kliki w idealne wykresy. Jak dotąd jedyne znane algorytmy wielomianowe dla tych problemów oparte są na elipsoidzie, która jest „powolna” (i niestabilna numerycznie).
Test pierwotności AKS w czasie . Chociaż wiele ulepszeń (obecnie ), algorytm AKS jest nadal zbyt wolny w praktyce. $O((\log n)^{12})$ $O((\log n)^{7.5})$

— vb le
źródło

Tak, to bardzo dobre przykłady!

— Juho

Zauważ, że istnieją bardzo szybkie znane algorytmy do testowania pierwotności, jeśli dozwolone jest randomizowanie. Mówiąc praktycznie, nie spełnia kryteriów, że „najszybszy znany algorytm działa wolno”.

— 6005

11

Pozostaje podobne pytanie cstheory , z wieloma przykładami, od algorytmów „realistycznie niepraktycznie wolnych” z wykładnikiem od 6 do 7 w górę. To pytanie dotyczy także dużych stałych.

Jest jeden klasyk, który chcę odtworzyć, ponieważ wydaje się, że jest to tak okropnie okropny przykład czasu wielomianowego (bezwstydnie skradziony z odpowiedzi JeffE):

Następstwo 1. Liczba kroków w naszym algorytmie wynosi najwyżej . $1752484608000n^{79}L^{25}/D^{26}(\Theta_0)$

$117607251220365312000n^{79}(\ell_{max}/d_{min}(\Theta_0))^{26}.$

Od: Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, James F. O'Brien, Podejście energetyczne do rozwijania powiązań , SOCG 2004.

— Luke Mathieson
źródło

Zastanawiam się, czy to naprawdę problem praktyczny. Ponadto lista problemów w CSTheory jest krótka, a większość problemów wydaje się dość ezoteryczna ... :-(

— Juho

@Juho w dalszym komentarzu do drugiego pytania znajduje się kolejny link do innego podobnego pytania na math.se. Znalazłem ten, który odtworzyłem, zbyt zabawny, aby mu się oprzeć, ale istnieją pewne ważne wyniki ptime, które mają straszne algorytmy lub niekonstruktywne: Twierdzenie Courcelle'a i kilka podobnych metatheoremów sprawdzających model, wiele drobnych rzeczy na grafie i algorytmy dekompozycji dla właściwości takie jak szerokość.

— Luke Mathieson,