EXP-vollständige Probleme gegen subexponentielle Algorithmen

10

Bedeutet die Tatsache, dass ein Problem EXP-Zeit vollständig ist, dass A nicht in D T I M E ( 2 o ( n ) ) ist ?AADTIME(2o(n))

Mir ist bewusst, dass nach dem Zeithierarchiesatz nicht in E = D T I M E ( 2 O ( n ) ) enthalten ist . Dies scheint jedoch die Existenz subexponentieller Zeitalgorithmen für jedes EXP-vollständige Problem A nicht sofort auszuschließen , da beim Reduzieren einer Instanz x eines Problems B E X P.EXP=DTIME(2nO(1))E=DTIME(2O(n))AxBEXPIn einem Fall von Problem kann es zu einem Polynom kommen. Mit anderen Worten, | y | = | x | O ( 1 ) .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.

Überprüfung
quelle
11
Im Gegenteil, ein triviales Auffüllargument zeigt, dass für jedes EXP-vollständige Probleme existieren, die in der Zeit 2 n comp berechenbar sind . ϵ>02nϵ
Emil Jeřábek
7
@ 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:

12

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

ϵ>0DTIME(2nϵ)L2ncd>c/ϵ

L={0m#w:wL,m|w|d}.
LLw0|w|d#wL

L2nϵn0m#wmndn=|w|wL2nc2mc/d2mϵ2nϵ


AC0|w|

Emil Jeřábek
quelle