Сложнее всего известная естественная проблема в P?

Интересно, какое (в настоящее время) наибольшее число , такое, что естественная проблема известна со следующими свойствами:$k$

1. алгоритм уже нашел для этой проблемы.$O(n^k)$

2. Для любого фиксированного никакой алгоритм не известен для той же задачи. (Обратите внимание, что существовать более быстрый алгоритм , просто он еще не известен, поэтому я не ищу проверенную нижнюю границу.)$\epsilon>0$$O(n^{k-\epsilon})$$may$

3. Само описание проблемы не зависит от . (Это условие необходимо для исключения параметризованных случаев, таких как «найти клику размера во входном графе для константы ».)$k$$k$$k$

В некотором смысле, такая проблема может квалифицироваться как самая сложная, известная, естественная проблема в (относительно показателя наиболее быстрого известного алгоритма).$\bf P$

Алгоритм тестирования АКС простоты может быть хорошим кандидатом, где лучший алгоритм в настоящее время известный вариант алгоритма имеет время работы. См. Проверка на примитивность с гауссовскими периодами (Lenstra и Pomerance).$\tilde{O}(n^6)$

Как насчет нахождения двух непересекающихся кратчайших путей , которые имеют время выполнения ?$O(|V|^8)$

Также известен алгоритм для независимого множества в графах.$O(|V|^{12}\cdot |E|)$$P_5$

совершенные графы кажутся фундаментальными и поэтому «естественными» для теории сложности / математики во многих отношениях. то алгоритм распознавания работает в время . кажется возможным, что существуют другие «естественные» или «фундаментальные» графовые классы, которые распознаются дольше и все еще находятся в P.$O(|V(G)|^9)$