Pemecah NP yang optimal

Perbaiki masalah pencarian NP-complete misalnya bentuk pencarian SAT. Pencarian Levin menyediakan algoritma L untuk menyelesaikan X yang dalam beberapa hal optimal. Secara khusus, algoritma ini adalah "Jalankan semua program yang mungkin P dalam menyesuaikan pada input x , setelah beberapa P mengembalikan jawaban y menguji apakah itu benar". Ini optimal dalam arti bahwa diberikan program P yang memecahkan X dengan kompleksitas waktu t $X \subset \lbrace 0,1 \rbrace^* \times \lbrace 0,1 \rbrace^*$$L$$X$$P$$x$$P$$y$$P$$X$ , waktu kompleksitas t L ( n ) dari L memenuhi$t_P(n)$$t_L(n)$$L$

$$t_L(n) < 2^{|P|}p(t_P(n))$$

di mana adalah polinomial tetap yang tergantung pada model perhitungan yang tepat$p$

Optimalitas L dapat dirumuskan dengan cara yang agak lebih kuat. Yaitu, untuk setiap M ⊂ { 0 , 1 } * dan Q program pemecahan X dengan janji M dalam waktu t M Q ( n ) , kompleksitas waktu t M L ( n ) dari L terbatas masukan dalam M memenuhi$L$$M \subset \lbrace 0,1 \rbrace^*$$Q$$X$$M$$t^M_Q(n)$$t_L^M(n)$$L$$M$

$$t_L^M(n) < 2^{|Q|}q(n, t^M_Q(n))$$

di mana adalah polinom tetap. Perbedaan penting adalah bahwa t M Q ( n ) dapat misalnya jumlahnya banyak bahkan jika P ≠ N $q$$t^M_Q(n)$$P \neq NP$

"Kelemahan" yang jelas dari adalah faktor besar 2 | Q | dalam ikatan ini. Sangat mudah untuk melihat bahwa jika ada algoritma yang memenuhi batas dari bentuk yang sama dengan 2 | Q | digantikan oleh polinomial dalam | Q | maka P = N P . Ini karena kita dapat menganggap Q sebagai program yang memecahkan beberapa contoh X dengan mengkodekan jawabannya. Begitu pula jika 2 | Q | dapat diganti dengan fungsi sub-eksponensial | Q $L$$2^{|Q|}$$2^{|Q|}$$|Q|$$P = NP$$Q$$X$$2^{|Q|}$$|Q|$maka hipotesis waktu eksponensial dilanggar. Namun, jawaban untuk pertanyaan berikut kurang jelas (bagi saya):

Dengan asumsi hipotesis waktu eksponensial dan dugaan terkenal lainnya (misalnya non-degenerasi hierarki polinomial, keberadaan fungsi satu arah) jika perlu, apakah ada algoritma penyelesaian X st untuk setiap M ⊂ { 0 , 1 } ∗ dan Q program pemecahan X dengan janji M dalam waktu t M Q ( n ) , kompleksitas waktu t M A ( n ) dari A dibatasi untuk masukan dalam M memenuhi$A$$X$$M \subset \lbrace 0,1 \rbrace^*$$Q$$X$$M$$t^M_Q(n)$$t_A^M(n)$$A$$M$

$$t_A^M(n) < f(|Q|)q(n, t^M_Q(n)) + g(|Q|)$$

di mana adalah polinomial, f adalah sub-eksponensial dan g adalah arbitrer$q$$f$$g$

Jika jawabannya positif, bisakah polinomial? Berapa tingkat pertumbuhan g (jelas setidaknya eksponensial di bawah ETH)? Jika jawabannya negatif, bisakah polinom f ada jika ETH salah tetapi P ≠ N P ?$f$$g$$f$$P \neq NP$

Pertimbangkan algoritma berikut (varian dari algoritma Levin):

$n$

Berhenti ketika salah satu algoritma menemukan solusi.

$x$$n$

• $Q$$n$$O(n \cdot t^M_Q(n)) \cdot \mathrm{poly}(n)$

• $Q$$n$$n < 2^{|Q|}$$2^{n^{O(1)}} = 2^{2^{O(|Q|)}}$

$$t^M_A(n) \leq \mathrm{poly}(n) \cdot t^M_Q(n) + 2^{2^{O(|Q|)}}.$$

$f(n)$$g(n)$$n$$g(n)$$n$$f(n)$$n$