Pemecah masalah universal yang efisien?

Tetapkan "masalah" menjadi algoritma menerima bilangan alami dan mengembalikan 0 atau 1 yang mengembalikan pada setidaknya satu . Setiap tersebut disebut sebagai "solusi" untuk $A$ $1$ $n \in \mathbb{N}$ $n$ $A$

Tetapkan "pemecah masalah universal" menjadi algoritme menerima masalah dan mengembalikan salah satu solusinya. Misalnya, dapat bekerja dengan perulangan atas semua bilangan dan berjalan masukan pada mereka sampai hasil (hanya memiliki berhenti pada input yang valid) $U$ $U$ $1$

Saya tertarik menjelajahi batasan kinerja pada pemecah masalah universal

Diberikan pemecah masalah universal dan masalah, menyatakan waktu yang dibutuhkan untuk menghasilkan output setelah menerima input $U$ $A$ $t(U, A)$ $U$ $A$

Pemecah masalah universal disebut "efisien" ketika untuk setiap pemecah masalah universal , kami memilikinya $U$ $V$

t (U, A) < t (V, A) + t_{V}

$t(U, A) < t(V, A) + t_V$

Di sini tergantung pada tetapi tidak tergantung pada $t_V$ $V$ $A$

Apakah ada pemecah masalah universal yang efisien?

EDIT: Saya menyadari adalah mungkin untuk mengubah definisi "masalah" dan "pemecah masalah universal" menjadi sesuatu yang sedikit lebih elegan dan pada dasarnya setara. "Masalah" adalah algoritma tanpa input yang mengembalikan 0 atau 1 (yang berhenti). "Pemecah masalah universal" adalah algoritma yang menerima masalah dan mengembalikan hasilnya. Ini lebih atau kurang mesin Turing universal

Definisi lama dapat dikurangi dengan definisi baru, karena diberikan masalah dalam arti tua, kita dapat membangun masalah dalam arti baru yang hanya berlaku sepele lama-rasa masalah universal pemecah ke (solver dijelaskan dalam teks di atas ) $A$ $B$ $A$

Definisi baru dapat direduksi menjadi definisi lama, karena mengingat masalah dalam pengertian baru, kita dapat membangun masalah dalam pengertian lama yang hanya menghitung dan membandingkan input ke hasilnya $B$ $A$ $B$

Contoh sepele dari pemecah masalah universal rasa baru adalah algoritma yang hanya menjalankan inputnya

cc.complexity-theory ai.artificial-intel Vanessa
sumber

Jawaban:

Tidak ada pemecah masalah universal yang efisien. Secara intuitif, U harus memiliki (hampir) runtime optimal untuk setiap masalah keputusan yang dapat ditentukan; sementara teorema speedup mengatakan bahwa ada masalah keputusan yang dapat ditentukan yang tidak memiliki algoritma optimal (bahkan dalam arti yang sangat ringan). Untuk memformalkan ini:

Teorema percepatan waktu (lihat misalnya [1])): Untuk setiap fungsi yang dapat dihitung (dan super-linier) terdapat himpunan yang dapat ditentukan sehingga jika maka untuk memuaskan . $g$ $S$ $S \in DTIME(t)$ $S \in DTIME(t')$ $t'$ $g(t'(n)) < t(n)$

Berikut ini, kami bekerja dengan definisi kedua. Biarkan menjadi masalah pemecah universal. Mari dan menjadi algoritma yang memutuskan . Biarkan menjadi no input TM st . Ada TM dengan tentang kelebihan logaritmik dalam runtime (Pengodean dan hanya berbeda ). Dengan speed-up thoerem, ada TM yang menentukan dan . Jadi kita punya . $U$ $g(n)=2^{2n}$ $A$ $S$ $A_i$ $A_i = A(i)$ $\tilde U(i)=U(A_i)$ $A$ $A_i$ $O(\log i)$ $B$ $S$ $2^{ 2 TIME(B)} < TIME(\tilde U)$ $2^{TIME(B)} < TIME(\{U(A_i)\})$

Biarkan menjadi pemecah masalah universal sehingga untuk input , ia mensimulasikan dengan kelebihan logaritmik dalam waktu. (Jelas fungsi runtime dari dan tidak terikat) Jadi kita punya $V$ $A_i$ $B(i)$ $A(i)$ $B(i)$

$\forall c \; \exists A_i \;\; t(U, A_i) > t(V, A_i) +c$

Jadi tidak bisa efisien. $U$

[1] Oded Goldreich, Kompleksitas Komputasi, Perspektif Konseptual, teorema 4.8. Bab 4.2.1.2 juga relevan.

Ruhollah Majdoddin
sumber

Solusi hebat, thx!

Vanessa

Algoritma universal Levin adalah algoritma sedemikian rupa sehingga . Dengan memodifikasi algoritme (lihat misalnya Algoritma Hutter yang Tercepat dan Terpendek untuk Semua Masalah yang Didefinisikan dengan Baik ), Anda dapat menjadikan konstanta universal, meskipun jelas bukan seperti yang Anda butuhkan. Untuk pekerjaan terkait, konsultasikan pekerjaan dengan Hirsch, Itsykson dan siswa mereka, misalnya laporan teknis ini . $t(U,A) < s_V t(V,A) + t_V$ $s_V$ $1$

Sunting: Seperti komentar Squark, runtime dari algoritma Levin juga tergantung pada runtime dari , karena harus memverifikasi jawabannya. Untuk mendapatkan konstan , yang perlu Anda lakukan adalah mengatur kecepatan berbagai algoritma dalam progres geometrik (bukan progresi aritmatika, seperti dalam algoritma asli Levin). $A$ $s_V$

Yuval Filmus
sumber

Jika saya mengerti dengan benar, Levin's adalah sesuatu di sepanjang baris "mari kita jalankan semua kemungkinan algoritma secara paralel, dan setiap kali salah satu dari mereka menghasilkan jawaban mari kita mengujinya dan berhenti jika itu benar". Karena V adalah salah satu algoritme yang sedang dijalankan, V akan menemukan jawaban dalam waktu yang sama dengan V hingga perlambatan yang terkait dengan fraksi "waktu CPU" yang dialokasikan untuk "utas" V. Namun, saya pikir Anda kehilangan istilah tambahan A-dependent: waktu yang diperlukan untuk menguji jawaban. Algoritma Hutter bergantung pada pencarian bukti yang tidak cukup bagi saya karena saya tidak membuat asumsi tentang provabilitas

U

$U$

Vanessa

s_{V}

$s_V$

V

$V$

s_{V}

$s_V$

t_{V}

$t_V$

V

$V$

Saya tidak mengerti caranya. Btw jika saya menambahkan kondisi V terbukti merupakan pemecah masalah universal, akan mungkin untuk menghilangkan istilah dependen A dengan menjalankan hanya algoritma yang dapat dibuktikan sebagai pemecah masalah universal

Vanessa