Apakah mungkin untuk memutuskan apakah algoritma yang diberikan optimal secara asimptotik?

Apakah ada algoritma untuk masalah berikut:

Diberikan mesin Turing yang menentukan bahasa , Apakah ada mesin Turing memutuskan sedemikian rupa sehingga ? $M_1$ $L$
$M_2$ $L$ $t_2(n) = o(t_1(n))$

Fungsi dan adalah waktu menjalankan terburuk dari mesin Turing dan masing-masing. $t_1$ $t_2$ $M_1$ $M_2$

Bagaimana dengan kompleksitas ruang?

complexity-theory computability undecidability decision-problem StaticBug
sumber

Jawabannya jelas tidak. Menentukan waktu menjalankan kasus terburuk dari TM diketahui tidak dapat diputuskan.

chazisop

Pertanyaan yang lebih umum .

Raphael

Jawaban:

Berikut ini adalah argumen sederhana untuk menunjukkan bahwa mereka tidak dapat diputuskan, yaitu tidak ada algoritma untuk memeriksa apakah algoritma yang diberikan optimal mengenai waktu penggunaan atau penggunaan memorinya.

Kami mengurangi masalah penghentian pada pita kosong untuk masalah Anda tentang optimalitas waktu berjalan.

Biarkan menjadi mesin Turing yang diberikan. Biarkan N menjadi mesin Turing berikut: $M$

: pada input 1. Jalankan pada pita kosong untuk (paling banyak) langkah. 2. Jika tidak berhenti dilangkah , jalankan loop ukuran , lalu kembali NO. 3. Kalau tidak, kembalikan YA. $N$ $n$
$M$ $n$
$M$ $n$ $2^n$

Ada dua kasus:

Jika tidak berhenti pada pita kosong, mesin akan berjalan selama menginjak input . Jadi waktu menjalankannya adalah . Dalam hal ini, jelas tidak optimal. $M$ $N$ $\Theta(2^n)$ $n$ $\Theta(2^n)$ $N$
Jika berhenti pada pita kosong, maka mesin akan berjalan untuk jumlah langkah konstan untuk semua cukup besar , sehingga waktu berjalan adalah . Dalam hal ini, jelas optimal. $M$ $N$ $n$ $O(1)$ $N$

Pendeknya:

M halts on blank tape \Leftrightarrow N is optimial

$M \text{ halts on blank tape } \Leftrightarrow N \text{ is optimial }$

Selain itu diberikan kode untuk kita dapat menghitung kode untuk . Karenanya kami mengalami pengurangan dari penghentian masalah pada pita kosong ke masalah waktu berjalan yang optimal. Jika kita bisa memutuskan apakah mesin Turing yang diberikan optimal, kita bisa menggunakan reduksi di atas untuk memeriksa apakah mesin yang diberikan berhenti pada pita kosong. Karena berhenti pada pita kosong tidak dapat dipastikan, masalah Anda juga tidak dapat diputuskan. $M$ $N$ $N$ $M$

Argumen serupa dapat digunakan untuk ruang, yaitu juga tidak dapat dipastikan untuk memeriksa apakah mesin Turing yang diberikan optimal mengenai ruang yang digunakannya.

Bahkan pernyataan yang lebih kuat adalah benar: kita tidak dapat memutuskan apakah fungsi yang dapat dihitung adalah batas atas pada kompleksitas waktu dari komputasi fungsi yang dapat dihitung. Begitu pula untuk ruang. Yaitu bahkan teori kompleksitas dasar tidak dapat diotomatisasi oleh algoritma (yang dapat dianggap sebagai berita baik untuk teori kompleksitas;).

Kaveh
sumber

Hanya ingin menyebutkan bahwa dalam pertanyaan awal, OP berasumsi bahwa

memutuskan bahasa dalam waktu kuadratik.

M_{1}

$M_1$

Pål GD

Harap jelaskan bahwa Anda melihat optimalitas asimptotik . Bahkan dalam kasus 2,

tidak sepenuhnya optimal; fungsi

dapat dihitung dalam satu langkah, sedangkan

membutuhkan lebih dari

(untuk

besar ), dengan

panjang perhitungan

pada pita kosong.

n

$n$

n \mapsto YES

$n \mapsto \textrm{YES}$

N

$N$

n_{0}

$n_0$

n

$n$

n_{0}

$n_0$

M

$M$

Raphael

Ah, pertanyaannya berubah sejak saya terakhir membacanya. Sudahlah.

Raphael

@ PålGD, saya pikir OP menggunakan itu sebagai contoh (berdasarkan pertanyaan asli yang diposting di cstheory). Anda dapat memeriksa komentar di bawah pertanyaan itu.

Kaveh

Seperti yang disebutkan orang lain jawabannya adalah tidak.

Tetapi ada artikel menarik yang ditulis oleh Blum " Teori Mesin-Independen dari Kompleksitas Fungsi Rekursif ". Dia menunjukkan bahwa ada beberapa fungsi dengan properti yang tidak peduli seberapa cepat suatu program untuk menghitung fungsi-fungsi ini ada program lain untuk menghitung mereka sangat jauh lebih cepat .

properti yang sangat bagus!

Reza
sumber

-3

Ha! Jika jawabannya ya, kita akan hidup di dunia yang berbeda.

$A_0$ $A$ $L$ $A_0$ $A$

Sayangnya, ini tidak mungkin, dan memang saya pribadi menganggap pembuktian (non-sepele) optimalitas adalah masalah paling menarik (dan sulit) dalam ilmu komputer. Sejauh yang saya tahu - saya akan senang untuk dikoreksi - tidak ada hasil optimal untuk masalah polinomial (kecuali hasil optimalitas sepele tentu saja algoritma mengambil waktu sebanding dengan ukuran input).

t ke t
sumber

Ω (N)

$\Omega(N)$

Ω (n \log n)

$\Omega(n \log n)$

@vonbrand - itulah yang saya maksud dengan algoritma yang proporsional dengan ukuran input.

t ke t

@Tetapi Ok, aku khawatir ini tidak akan membuahkan hasil, tetapi aku akan mencoba lagi. 1) Tidak, tidak sama sekali. Jika Anda hanya menyimpan satu langkah pada setiap input, Anda memiliki algoritma yang lebih baik dari sebelumnya, meskipun memiliki runtime asimptotik yang sama. 2) Tidak, tidak. Ini juga bisa berarti "Saya tidak tahu, tetapi jika ya, maka X". Ini tidak biasa (cf P? = NP). 3) Anda mengklaim tidak ada batas bawah non-sepele (pada asimptotik, saya kira) sama sekali . Itu salah. Tolong kerjakan pekerjaan rumah Anda.

Raphael

@ MartinJonáš Maksud saya mesin Turing 2-tape. Kaveh ada benarnya, bukti dari teorema hierarki waktu memang memberikan masalah yang dapat dipecahkan dengan waktu yang rumit dengan kompleksitas tinggi, tetapi contoh-contohnya tidak alami dan tidak terasa terlalu eksplisit. Juga, tidak ada hierarki yang diketahui untuk waktu probabilistik, jadi di sana kita tidak punya apa-apa.

Sasho Nikolov