Masalah Lengkap EXP vs Algoritma Subeksponensial

Apakah fakta bahwa masalah adalah waktu EXP lengkap berarti bahwa tidak ada dalam ?A D T I M E ( 2 o ( n )$A$$A$$DTIME(2^{o(n)})$

Saya sadar bahwa menurut teorema hierarki waktu, tidak termasuk dalam . Namun demikian ini tampaknya tidak mengecualikan segera keberadaan algoritma waktu sub-eksponensial untuk setiap EXP-menyelesaikan masalah , karena ketika mengurangi instance dari masalah ke instance y dari masalah , kita mungkin memiliki polinomial meledak dalam ukuran. Dengan kata lain, .E = D T I M E ( 2 O ( n ) ) A x B ∈ E X P A | y | = | x | O ( 1 $EXP=DTIME(2^{n^{O(1)}})$$E=DTIME(2^{O(n)})$$A$$x$$B\in EXP$$A$$|y|=|x|^{O(1)}$

Jadi pertanyaan saya adalah apakah ada beberapa argumen yang mengesampingkan, tanpa syarat, keberadaan algoritma waktu sub-eksponensial untuk masalah lengkap EXP.

Karena banyaknya permintaan, saya mengubah komentar saya menjadi sebuah jawaban.

Argumen padding sederhana menunjukkan bahwa untuk setiap konstanta , ada masalah EXP-complete di . Memang, perbaiki masalah lengkap -EXP yang sewenang-wenang , dan asumsikan bahwa itu dapat dihitung dalam waktu . Biarkan , dan pertimbangkan masalah Di satu sisi, adalah polinomial-time direduksi menjadi melalui fungsi , dengan demikian EXP-hard.D T I M E ( 2 n ϵ ) L 2 n c d > c / ϵ L ′ = { 0 m # w : w ∈ L , m ≥ | w | d } . $\epsilon>0$$\mathrm{DTIME}(2^{n^\epsilon})$$L$$2^{n^c}$$d>c/\epsilon$

Di sisi lain, dapat dihitung dalam waktu : diberi input ukuran , kami pertama-tama memeriksa (dalam waktu polinomial) apakah itu dalam bentuk untuk , di mana. Kemudian kita periksa apakah , yang membutuhkan waktu .2 n ϵ n 0 m # w m ≥ n ′ d n ′ = | w | w ∈ L 2 n ′ c ≤ 2 m c / d ≤ 2 m ϵ ≤ 2 n $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}$

A C 0 | w ${}^\dagger$ Sebenarnya, reduksi yang diberikan bahkan seragam , dan itu bisa dibuat DLogTime jika kita menggantidengan batas atas yang merupakan kekuatan dua.$\mathrm{AC}^0$$|w|$