Probleme mit unbekannten einzelnen Exponentialzeitagorithmen

Ich suche nach Beispielen für Probleme, bei denen es einfach ist, Algorithmen in der Zeit oder 2 O ( n c ) für einige c > 1 zum Laufen zu bringen , für die jedoch nicht bekannt ist, ob es eine gibt Algorithmus läuft in Zeit 2 O ( n ) .$2^{O(n\log n)}$$2^{O(n^c)}$$c>1$$2^{O(n)}$

Ich interessiere mich hauptsächlich für graphentheoretische Probleme, aber auch andere schöne Beispiele wären willkommen.

Zum Beispiel ist es trivial, einen Algorithmus zu entwickeln, der in der Zeit für das Hamilton- Pfadproblem läuft . Testen Sie einfach alle Permutationen. Mit dynamischer Programmierung kann man jedoch die Zeit 2 O ( n ) erreichen . Gibt es andere natürliche Konnektivitätsprobleme oder Variationen des Hamilton-Pfadproblems, für die kein Algorithmus bekannt ist, der in der Zeit 2 O ( n ) läuft?$O(n!) = 2^{O(n\log n)}$$2^{O(n)}$$2^{O(n)}$

In dem Graph Homomorphism Problem ist die Eingabe zwei Graphen und H und die Frage ist, ob es eine Abbildung h von den Eckpunkten von G zu den Eckpunkten von H gibt, so dass wir für jede Kante u v ∈ E ( G ) das h haben ( u ) h ( v ) ∈ E ( H ) .$G$$H$$h$$G$$H$$uv\in E(G)$$h(u) h(v)\in E(H)$

Das Problem kann in der Zeit durch einen Brute-Force-Algorithmus gelöst werden (die O ∗ -Notation verbirgt Polynomfaktoren in der Eingabegröße).$O^*(|V(H)|^{|V(G)})$$O^*$

Es ist jedoch offen, ob es in der Zeit gelöst werden kann , und dies erscheint als offene Frage in$O^*(c^{|V(H)|+|V(G)|})$

• Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch: Genaue Algorithmen für Graphhomomorphismen . Theorie Comput. Syst. 41 (2): 381 & ndash; 393 (2007)

Permutationsisomorphismus von Permutationsgruppen, auch bekannt als Permutationsgruppenkonjugation:

Eingabe: Zwei Listen von Permutationen in , sagen wir ( π 1 , … , π k ) und ( ρ 1 , … , ρ ℓ$S_n$$(\pi_1, \dotsc, \pi_k)$$(\rho_1, \dotsc, \rho_\ell)$

Output: Eine Permutation , so dass π - 1 ⟨ π 1 , ... , π k ⟩ π = ⟨ & rgr; 1 , ... , & rgr; l ⟩ oder "nicht isomorph"$\pi \in S_n$$\pi^{-1} \langle \pi_1, \dotsc, \pi_k \rangle \pi = \langle \rho_1, \dotsc, \rho_\ell \rangle$

(wobei bedeutet die Untergruppe , die durch die π i ).$\langle \pi_1, \dotsc, \pi_k \rangle$$\pi_i$

Wie beim Beispiel des Hamilton-Pfades gibt es ein triviales Algorithmus. Das derzeit bekannteste ist 2 O ( n ) | G | O ( 1 ) wobei G = ⟨ π 1 , ... , π k ⟩ . Beachten Sie, dass | G | kann so groß wie n sein ! (trivial: G = S $n! = 2^{O(n \log n)}$$2^{O(n)} |G|^{O(1)}$$G = \langle \pi_1, \dotsc, \pi_k \rangle$$|G|$$n!$$G = S_n$) oder sogar für nichttriviales G (siehe z. B. das O'Nan-Scott-Theorem ). * Entfernen der Abhängigkeit von | G | wurde dort als wichtiges offenes Problem belassen.$n! / n^{O(1)}$$G$$|G|$

* - Trotz der Tatsache, dass groß sein kann, so dass dies im schlimmsten Fall asymptotisch nicht besser als trivial zu sein scheint, stellt sich heraus, dass 2 O ( n ) | G | O ( 1 ) war genau das, was für den Polynom-Zeit-Isomorphismus-Test von Gruppen ohne normale abelsche Untergruppen benötigt wurde.$G$$2^{O(n)}|G|^{O(1)}$

Berechnung der Kreuzungsnummer eines Graphen. Bestehende exakte Algorithmen beinhalten die Formulierung als ganzzahliges lineares Programm mit einer Anzahl von Variablen, die in der Anzahl der Kanten kubisch sind [Chimani et al., ESA 2008] . Selbst für die eingeschränkte einseitige Kreuzungszahl, bei der die Eckpunkte an der Grenze einer Platte und den Kanten innerhalb der Platte platziert sind, sind bekannte Algorithmen in exponentiell und nicht einfach exponentiell [Bannister et al , GD 2013] .$O(n\log n)$