Problemy decyzyjne w

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 ).n O ( n 9$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.

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 O ( ( log n ) 7.5 ) ), algorytm AKS jest nadal zbyt wolny w praktyce.$O((\log n)^{12})$$O((\log n)^{7.5})$

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.