Masalah keputusan sehingga algoritma apa pun mengakui algoritma yang lebih cepat secara eksponensial

Dalam Algoritma Hromkovič untuk Masalah Sulit (edisi ke-2) ada teorema ini (2.3.3.3, halaman 117):

Ada masalah keputusan (decidable) sehingga untuk setiap algoritma yang memecahkan ada algoritma lain yang juga memecahkandan juga memenuhi $P$ $A$ $P$ $A'$ $P$
$\qquad \forall^\infty n \in \mathbb{N}. \mathrm{Time}_{A'}(n) = \log_2 \mathrm{Time}_A(n)$

$\mathrm{Time}_A(n)$ adalah runtime terburuk dari masukan ukuran dan berarti "untuk semua tapi finitely banyak". $A$ $n$ $\forall^\infty$

Bukti tidak diberikan dan kami tidak tahu bagaimana cara melakukannya; sebenarnya cukup kontra-intuitif. Bagaimana teorema itu dapat dibuktikan?

complexity-theory Raphael
sumber

Untuk judul, mungkin kira-kira seperti: "Apakah ada masalah keputusan untuk memperbaiki algoritma penyelesaian apa pun?" Yang sedang berkata, itu hanya sebuah tembakan dalam kegelapan, tetapi bukankah itu bisa menjadi kasus yang merosot untuk masalah keputusan sepele? Entah bagaimana, jika Anda mengubah kesetaraan, itu berarti bahwa selalu mungkin untuk menyelesaikan masalah dengan cara "terburuk" (dengan melakukan langkah-langkah yang tidak berguna). Tapi itu hanya dugaan.

Charles

Jawaban:

Tampaknya ini adalah kasus sederhana dari Blum's Speedup Theorem :

Diberikan ukuran kompleksitas Blum dan total fungsi yang dapat dihitung dengan dua parameter, maka ada total predikat yang dapat dihitung (fungsi yang diperhitungkan dengan nilai Boolean) sehingga untuk setiap program untuk , terdapat program untuk sehingga untuk hampir semua $(\varphi, \Phi)$ $f$ $g$ $i$ $g$ $j$ $g$ $x$
$f (x, Φ_{j} (x)) \leq Φ_{saya} (x)$ $f(x,\Phi_j(x)) \leq \Phi_i(x)$

Biarkan saja ukuran kompleksitas menjadi ukuran kompleksitas waktu (yaitu adalah kompleksitas waktu dari mesin Turing dengan kode ) dan misalkan . $\Phi_e(x)$ $e$ $f(x,y) = 2^y$

Kaveh
sumber

+1: Berikut ini tautan ke makalah aslinya: logic.cse.unt.edu/tarau/teaching/SoftEng/OLD/papersToDiscuss/… .

Aryabhata