Le problème naturel le plus difficile connu de P?

Je me demande quel est actuellement le plus grand nombre , de sorte qu'un problème naturel ayant les propriétés suivantes soit connu:$k$

1. Un algorithme a déjà été trouvé pour le problème.$O(n^k)$

2. Pour tout fixe pas de O ( n k - ε ) algorithme est connu pour le même problème. (Notez qu'un algorithme plus rapide m un y exist, juste on ne sait pas encore, donc je ne suis pas à la recherche d'une limite inférieure éprouvée.)$\epsilon>0$$O(n^{k-\epsilon})$$may$

3. La description du problème ne dépend pas de . (Cette condition est nécessaire pour exclure les cas paramétrés tels que "trouver une clique de taille k dans un graphe en entrée, pour une constante k ".)$k$$k$$k$

En un sens, un tel problème pourrait être considéré comme le problème le plus difficile, connu et naturel de (en ce qui concerne l'exposant de l'algorithme le plus rapide connu).$\bf P$

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

$O(|V|^8)$

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

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