Entscheidungsprobleme in

Was sind einige Beispiele für schwierige Entscheidungsprobleme, die in der Polynomzeit gelöst werden können? Ich suche nach Problemen, bei denen der optimale Algorithmus "langsam" ist oder bei denen der schnellste bekannte Algorithmus "langsam" ist.

Hier sind zwei Beispiele:

• Erkennen perfekter Grafiken. In ihrer FOCS'03-Arbeit [1] Cornuéjols gaben Liu und Vuskovic einen -Zeitalgorithmus für das Problem an, wobei n die Anzahl der Eckpunkte ist. Ich bin nicht sicher, ob diese Grenze verbessert wurde, aber nach meinem Verständnis ist mehr oder weniger ein Durchbruch erforderlich, um einen schnelleren Algorithmus zu erhalten. (Die Autoren geben einen O ( n 9 ) -Zeitalgorithmus in der Journalversion von [1] an, siehe hier ).$O(n^{10})$$n$$O(n^9)$

• Erkennung von Kartendiagrammen. Thorup [2] gab einen ziemlich komplexen Algorithmus mit einem Exponenten von (ungefähr?) . Vielleicht wurde dies sogar dramatisch verbessert, aber ich habe keine gute Referenz.$120$

Ich interessiere mich besonders für Probleme, die von praktischer Bedeutung sind, und das Erhalten eines "schnellen" (oder sogar praktischen) Algorithmus ist seit mehreren Jahren offen.

[1] Cornuéjols, Gérard, Xinming Liu und Kristina Vuskovic. "Ein Polynomalgorithmus zum Erkennen perfekter Graphen." Grundlagen der Informatik, 2003. Verfahren. 44. jährliches IEEE-Symposium am. IEEE, 2003.

[2] Thorup, Mikkel. Msgstr "Diagramme in Polynomzeit abbilden." Grundlagen der Informatik, 1998. Verfahren. 39. Jährliches Symposium am. IEEE, 1998.

Vielleicht passen die folgenden Probleme in Ihre Beispiele:

• (Die Entscheidungsversion von) Coloring, Clique, Stable Set, Clique Covering in perfekten Grafiken. Bisher basieren die einzigen bekannten polynomiellen Zeitalgorithmen für diese Probleme auf der Ellipsoidmethode, die langsam (und numerisch instabil) ist.

• $O((\log n)^{12})$$O((\log n)^{7.5})$

Bei cstheory gibt es eine ähnliche Frage , mit vielen Beispielen, die von den "realistisch unpraktisch langsamen" Algorithmen mit Exponenten von 6 oder 7 aufwärts reichen. Diese Frage behandelt auch große Konstanten.

Es gibt einen Klassiker, den ich reproduzieren möchte, da er wie ein solch spektakulär schreckliches Beispiel für die Polynomzeit erscheint (schamlos aus JeffEs Antwort gestohlen):

$1752484608000n^{79}L^{25}/D^{26}(\Theta_0)$

$117607251220365312000n^{79}(\ell_{max}/d_{min}(\Theta_0))^{26}.$

Aus: Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, James F. O'Brien, Ein energiegetriebener Ansatz zur Entfaltung von Verknüpfungen , SOCG 2004.