Das schwerste bekannte natürliche Problem in P?

Ich frage mich, was ist (derzeit) die größte Zahl , so dass ein natürliches Problem mit den folgenden Eigenschaften bekannt ist:$k$

1. Ein Algorithmus wurde für das Problem bereits gefunden.$O(n^k)$

2. Für jedes feste kein O ( n k - ε ) Algorithmus wird für das gleiche Problem bekannt. (Beachten Sie, dass ein schneller Algorithmus m a y exist, nur ist es noch nicht bekannt, so dass ich nicht für eine bewährte untere Grenze der Suche bin.)$\epsilon>0$$O(n^{k-\epsilon})$$may$

3. Die Problembeschreibung selbst hängt nicht von . (Diese Bedingung wird benötigt, um parametrisierte Fälle wie "Finde eine Clique der Größe k in einem Eingabediagramm für eine Konstante k " auszuschließen .)$k$$k$$k$

In gewissem Sinne könnte sich ein solches Problem als das schwierigste bekannte natürliche Problem in (in Bezug auf den Exponenten des schnellsten bekannten Algorithmus).$\bf P$

Der AKS-Primalitätstest-Algorithmus kann ein guter Kandidat sein, bei dem die derzeit bekannteste Version des Algorithmus eine Laufzeit von hat. Siehe Primalitätstests mit Gaußschen Perioden (Lenstra und Pomerance).$\tilde{O}(n^6)$

Wie wäre es , zwei unzusammenhängende kürzeste Pfade zu finden , die eine Laufzeit von $O(|V|^8)$ ?

Auch Algorithmus ist bekannt für unabhängige Menge in P 5 -freie Graphen.$O(|V|^{12}\cdot |E|)$$P_5$

Perfekte Graphen scheinen in vielerlei Hinsicht grundlegend und daher "natürlich" für die Komplexitätstheorie / Mathematik zu sein. der Erkennungsalgorithmus läuft in der Zeit . Es scheint möglich, dass es andere "natürliche" oder "grundlegende" Grafikklassen gibt, deren Erkennung länger dauert und die sich immer noch in P befinden.$O(|V(G)|^9)$