¿El problema natural más difícil conocido en P?

Me pregunto cuál es (actualmente) el número más grande , de modo que se conozca un problema natural con las siguientes propiedades:$k$

1. Un algoritmo ha sido ya encontrado para el problema.$O(n^k)$

2. Para cualquier algoritmo fijo no O ( n k - ϵ ) se conoce para el mismo problema. (Tenga en cuenta que un algoritmo más rápido m una y existir, simplemente no se sabe todavía, así que no estoy buscando una probada límite inferior).$\epsilon>0$$O(n^{k-\epsilon})$$may$

3. La descripción del problema en sí no depende de . (Esta condición es necesaria para excluir casos parametrizados como "encontrar una camarilla de tamaño k en un gráfico de entrada, para una constante k ").$k$$k$$k$

En cierto sentido, tal problema podría calificar como el problema más difícil, conocido y natural en (con respecto al exponente del algoritmo más rápido conocido).$\bf P$

$\tilde{O}(n^6)$

$O(|V|^8)$

$O(|V|^{12}\cdot |E|)$$P_5$

$O(|V(G)|^9)$