Najtrudniejszy znany problem naturalny w P?

Zastanawiam się, jaka jest (obecnie) największa liczba , tak że znany jest naturalny problem z następującymi właściwościami:$k$

1. algorytm został już, że do tego problemu.$O(n^k)$

2. Dla każdego ustalonego algorytmu no znany jest ten sam problem. (Zauważ, że istnieć szybszy algorytm , tylko nie jest jeszcze znany, więc nie szukam sprawdzonej dolnej granicy).$\epsilon>0$$O(n^{k-\epsilon})$$may$

3. Sam opis problemu nie zależy od . (Ten warunek jest potrzebny, aby wykluczyć sparametryzowane przypadki, takie jak „znajdź klikę o rozmiarze na wykresie wejściowym, dla stałej .”)$k$$k$$k$

W pewnym sensie taki problem można zakwalifikować jako najtrudniejszy, znany, naturalny problem w (dotyczący wykładnika najszybszego znanego algorytmu).$\bf P$

Algorytmu testowania AKS pierwszości może być dobrym kandydatem, przy czym najlepiej znane obecnie algorytm wersji algorytm czas pracy. Zobacz Testowanie pierwotności z okresami gaussowskimi (Lenstra i Pomerance).$\tilde{O}(n^6)$

Jak znaleźć dwie rozłączne najkrótsze ścieżki , które mają czas działania ?$O(|V|^8)$

Również algorytm jest znany z niezależnego zestawu w od .P $O(|V|^{12}\cdot |E|)$$P_5$

doskonałe wykresy wydają się być fundamentalne, a zatem „naturalne” dla teorii / matematyki złożoności na wiele sposobów. z algorytmu rozpoznawania działa w czasie . wydaje się możliwe, że istnieją inne „naturalne” lub „podstawowe” klasy grafów, których rozpoznanie zajmuje więcej czasu i nadal znajdują się w P.$O(|V(G)|^9)$