EXP-vollständige Probleme gegen subexponentielle Algorithmen

Bedeutet die Tatsache, dass ein Problem EXP-Zeit vollständig ist, dass nicht in ? $A$ $A$ $DTIME(2^{o(n)})$

Mir ist bewusst, dass nach dem Zeithierarchiesatz nicht in . Dies scheint jedoch die Existenz subexponentieller Zeitalgorithmen für jedes EXP-vollständige Problem nicht sofort auszuschließen , da beim Reduzieren einer Instanz eines Problems $EXP=DTIME(2^{n^{O(1)}})$ $E=DTIME(2^{O(n)})$ $A$ $x$ $B\in EXP$ In einem Fall von Problem kann es zu einem Polynom kommen. Mit anderen Worten, . $A$ $|y|=|x|^{O(1)}$

Meine Frage ist also, ob es ein Argument gibt, das die Existenz subexponentieller Zeitalgorithmen für EXP-vollständige Probleme bedingungslos ausschließt.

exp-time-algorithms complexity Überprüfung
quelle

Im Gegenteil, ein triviales Auffüllargument zeigt, dass für jedes

EXP-vollständige Probleme existieren, die in der Zeit

berechenbar sind .

ϵ > 0

$\epsilon>0$

2^{n^{ϵ}}

$2^{n^\epsilon}$

Emil Jeřábek

@ EmilJeřábek Danke. Ich denke, Ihr Kommentar ist die Antwort, nach der ich gesucht habe. Könnten Sie es bitte zu einer Antwort erweitern?

Überprüfung

Antworten:

Aufgrund der großen Nachfrage wandle ich meinen Kommentar in eine Antwort um.

$\epsilon>0$ $\mathrm{DTIME}(2^{n^\epsilon})$ $L$ $2^{n^c}$ $d>c/\epsilon$

L^{'} = {0^{m} # w : w \in L, m \geq | w |^{d}} .

$L'=\left\{0^m\#w:w\in L,m\ge|w|^d\right\}.$

L

$L$

^{†}

${}^\dagger$

L^{'}

$L'$

w \mapsto 0^{| w |^{d}} # w

$w\mapsto0^{|w|^d}\#w$

L^{'}

$L'$

$L'$ $2^{n^\epsilon}$ $n$ $0^m\#w$ $m\ge n'^d$ $n'=|w|$ $w\in L$ $2^{n'^c}\le2^{m^{c/d}}\le2^{m^\epsilon}\le2^{n^\epsilon}$

${}^\dagger$ $\mathrm{AC}^0$ $|w|$

Emil Jeřábek
quelle