Kelas Kompleksitas untuk Kasus Selain "Kasus Terburuk"

10

Apakah kita memiliki kelas kompleksitas sehubungan dengan, katakanlah, kompleksitas kasus rata-rata? Sebagai contoh, apakah ada kelas kompleksitas (bernama) untuk masalah yang membutuhkan waktu polinomial yang diharapkan untuk memutuskan?

Pertanyaan lain mempertimbangkan kompleksitas kasus terbaik , dicontohkan di bawah ini:

Apakah ada kelas masalah (alami) yang keputusannya membutuhkan setidaknya waktu eksponensial?

Untuk memperjelas, mempertimbangkan beberapa EXP bahasa -Lengkap . Jelas, tidak semua instance memerlukan waktu eksponensial: Ada contoh yang dapat diputuskan bahkan dalam waktu polinomial. Jadi, kompleksitas kasus bukanlah waktu yang eksponensial. $L$ $L$ $L$

EDIT: Karena beberapa ambiguitas muncul, saya ingin mencoba untuk lebih memperjelasnya. Dengan kompleksitas "kasus terbaik", maksud saya kelas kompleksitas yang kompleksitas masalahnya lebih rendah dibatasi oleh beberapa fungsi. Misalnya, definisikan BestE sebagai kelas bahasa yang tidak dapat diputuskan dalam waktu kurang dari eksponensial linear. Secara simbolis, misalkan menunjukkan mesin Turing yang berubah-ubah, dan , , dan adalah bilangan asli: $M$ $c$ $n_0$ $n$

$L \in \mathbf{BestE} \Leftrightarrow$ $\quad (\exists c)(\forall M)[(L(M) = L) \Rightarrow (\exists {n_0})(\forall n > {n_0})(\forall x \in {\{0,1\}^n})[T(M(x)) \ge {2^{c|x|}}]]$

di mana menunjukkan waktu yang dibutuhkan sebelum berhenti pada input . $T(M(x))$ $M$ $x$

Saya menerima bahwa mendefinisikan kelas masalah seperti itu sangat aneh, karena kami mensyaratkan bahwa, setiap mesin Turing , terlepas dari kekuatannya, tidak dapat memutuskan bahasa dalam waktu kurang dari beberapa eksponensial linier. $M$

Namun perhatikan bahwa rekanan polinomial-waktu ( BestP ) adalah alami, karena setiap mesin Turing memerlukan waktuuntuk setidaknya membaca inputnya. $|x|$

PS: Mungkin, alih-alih menghitung sebagai "untuk semua mesin Turing ," kita harus membatasinya pada beberapa kelas mesin Turing yang telah ditentukan, seperti mesin Turing polinomial waktu. Dengan begitu, kita dapat mendefinisikan kelas seperti , yang merupakan kelas bahasa yang membutuhkan setidaknya waktu kuadratik untuk diputuskan pada mesin Turing polinomial waktu. $M$ $\mathbf{Best(n^2)}$

PS2: Seseorang juga dapat mempertimbangkan rekan sirkuit-kompleksitas, di mana kami mempertimbangkan ukuran / kedalaman rangkaian terkecil untuk memutuskan bahasa.

cc.complexity-theory complexity-classes MS Dousti
sumber

Hanya karena ada contoh SAT yang mudah, itu tidak berarti bahwa waktu yang diharapkan adalah polinomial. Saya tidak yakin saya mengerti pertanyaan Anda ..

Lev Reyzin

@Lev Reyzin: Maksud saya SAT tidak diharapkan dalam waktu poli-waktu. Maksud saya karena SAT memiliki instance yang mudah, kita tidak dapat mengatakan bahwa kompleksitas "kasus terbaik" sulit.

MS Dousti

Oh, begitu, kompleksitas kasus rata-rata dan kompleksitas kasus terbaik adalah dua pertanyaan terpisah! Entah bagaimana saya melewatkan ini pada bacaan pertama saya - kesalahan saya.

Lev Reyzin

Saya tidak bisa menguraikan definisi BestE Anda. M dan x duduk di luar kuantifikasi mereka ... juga, tidakkah Anda ingin menolak input yang tidak dalam ?

M

$M$

L

$L$

Ryan Williams

@Ryan: Terima kasih telah menunjukkan kekurangannya. Saya memperbaikinya.

MS Dousti

13

Meskipun saya tidak dapat menguraikan definisi Anda, Anda harus tahu bahwa hierarki waktu yang lebih kuat diketahui, khususnya hierarki waktu "hampir di mana-mana".

Berikut adalah pernyataan formal: untuk setiap kali terikat , ada bahasa dengan properti yang setiap algoritma deterministik yang mengenali harus berjalan dalam waktu asimtotik lebih besar daripada pada semua tetapi banyak input, untuk waktu cukup kecil . $T(n)$ $L \in TIME[T(n)]$ $L$ $t(n)$ $t(n)$

"Cukup kecil" berarti . $t(n) \log t(n) \leq o(T(n))$

Misalkan kita memilih untuk contoh, dan memperoleh bahasa yang sulit . Kemudian, setiap algoritma yang mengenali dengan benar harus memakan waktu setidaknya pada semua input yang melewati panjang tertentu. Ini sepertinya yang Anda cari di kelas Anda BestE. $T(n)=2^n$ $L$ $L$ $2^n/n^2$

Referensi:

John G. Geske, Dung T. Huynh, Joel I. Seiferas: Catatan tentang Set Hampir-Di Mana Saja-Kompleks dan Memisahkan Kelas Deterministik-Kompleksitas Waktu Inf. Komputasi. 92 (1): 97-104 (1991)

Ryan Williams
sumber

Baiklah terima kasih. Saya pikir Anda cukup memahami pertanyaan saya, dan kalimat pengantar Anda, "Saya tidak bisa menguraikan definisi Anda" hanyalah tanda kerendahan hati Anda :)

MS Dousti

2

Asalkan saya menebak dengan benar, definisi Anda harus seperti: "L \ dalam BestE \ iff (\ ada c) (\ forall M) [(L (M) = L) \ Rightarrow (\ ada n_0) (\ forall n > n_0) (\ forall x \ in \ {0,1 \} ^ n) [T (M (x))> 2 ^ {c | x |})]. "

Ryan Williams

Yap, kamu benar. Saya mengedit definisi pada menit terakhir, dan salah menempatkan beberapa pengukur. Saya mengoreksi pertanyaan berdasarkan definisi Anda.

MS Dousti

12

Ada sejumlah kelas yang berusaha untuk mengatasi berbagai gagasan tentang kompleksitas kasus rata-rata. Di Complexity Zoo, beberapa kelas yang mungkin menarik bagi Anda adalah:

Arora / Barak mencakup banyak, kelas serupa (dalam Bab 18), mendefinisikan distP, distNP, dan sampNP.

Hubungan yang tepat antara semua kelas ini ditandai oleh Lima Dunia Impagliazzo, yang sebelumnya ditanyakan dalam pertanyaan lain .

Sejauh pertanyaan kompleksitas "kasus terbaik", saya tidak yakin saya cukup mengerti apa yang Anda maksud. Apakah Anda mencari EXP ?

Jika yang Anda maksud adalah kelas kompleksitas yang didefinisikan dalam hal run time kasus terbaik atas semua instance, ini bukan kompleksitas yang sangat baik untuk mengukur apriori, karena Anda hanya akan melihat kasus sepele dari masalah yang diberikan.

Daniel Apon
sumber

Bagus sekali! Itulah yang saya butuhkan untuk bagian kompleksitas kasus rata-rata dari pertanyaan. Mengenai bagian "kasus terbaik", saya perhatikan bahwa pernyataan asli dari pertanyaan itu tidak jelas. Salahku! Saya sudah banyak mengeditnya, jadi tolong pertimbangkan untuk membacanya lagi.

MS Dousti

5

[Memperluas jawaban Ryan Williams dan menambahkan beberapa istilah pencarian untuk Anda] Gagasan Anda tentang kerumitan kasus terbaik sudah memiliki nama: kekerasan di mana-mana (ae), atau bi-imunitas. (Contoh Ryan adalah dari -bi-imunitas). Jika adalah kelas kompleksitas, maka bahasa adalah jika tidak ada himpunan bagian tak terbatas sedemikian rupa sehingga . adalah -bi-imun jika dan komplemennya adalah $TIME[T(n)]$ $\mathcal{C}$ $L$ $\mathcal{C}$ $L' \subseteq L$ $L' \in \mathcal{C}$ $L$ $\mathcal{C}$ $L$ $\overline{L} = \Sigma^* \backslash L$ $\mathcal{C}$ -imun. Misalnya, tidak sulit untuk menunjukkan bahwa definisi Anda tentang setara dengan kelas set -bi-imun. $\mathbf{BestE}$ $E$

(Sejarah samping: gagasan kekebalan pertama kali dikembangkan oleh Post pada tahun 1944 dalam teori komputabilitas, jauh sebelum P bahkan didefinisikan. Post sebenarnya dianggap "set sederhana" - satu set sederhana jika komplemennya kebal. Untuk teori komputabilitas, kata "kebal" biasanya berarti "kebal terhadap set yang dapat dihitung." Dalam pengaturan itu, kekebalan setara dengan "kebal terhadap set ce" karena setiap set infinite berisi yang tidak dapat dihitung yang komputabel. Saya percaya makalah Post juga yang pertama kali memperkenalkan Gagasan tentang banyak-satu pengurangan, tetapi saya tidak bisa bersumpah untuk itu.)

Joshua Grochow
sumber

M

$M$

L

$L$

L

$L$

M (x) = 1

$M(x)=1$

L^{'}

$L'$

L^{'} \in C

$L' \in C$

1

@ Sadq: diperbaiki, terima kasih. @Ryan: Benar (atau beberapa jam yang lalu: ia telah memperbarui definisi). Maka itu akan menjadi kekebalan bukannya kekebalan. Either way, terutama saya hanya ingin menunjukkan kata kunci "kekebalan."

Joshua Grochow

2

Kasus yang berbeda lebih masuk akal ketika berbicara tentang algoritma, bukan masalah. Di sisi lain, kelas kompleksitas adalah tentang masalah, bukan algoritma. Oleh karena itu, kelas kompleksitas selalu menjadi kasus terburuk untuk algoritma apa pun karena definisi.

Dalam kompleksitas, tujuan Anda adalah untuk mengetahui jumlah sumber daya yang dibutuhkan untuk menyelesaikan setiap contoh masalah yang diberikan. Oleh karena itu, Anda tahu bahwa untuk setiap instance dan algoritma tertentu, Anda akan membutuhkan sumber daya tersebut dan tidak lebih.

Dalam analisis algoritme, tujuan Anda adalah memastikan algoritme Anda memiliki batas atas untuk sumber daya, dalam hal apa pun masalahnya. Batasan sepele adalah kelas kompleksitas masalah, karena tidak ada algoritma yang berguna (yang membuat langkah tidak tepat) membutuhkan waktu lebih lama dari itu. Namun, Anda dapat meningkatkan batasan yang diberikan spesifik algoritma.

$\Theta$

Adapun kasus terbaik, sepele untuk setiap masalah untuk menemukan paling sedikit sumber daya yang dibutuhkan. Asumsikan bahwa input adalah panjang O (n) dan output dari panjang O (m). Maka TM M berikut ini selalu berjalan di O (n) + O (m) untuk kasus terbaik:

M {Input, Instance, Solution}

Bandingkan instance yang diberikan dengan instance yang dikodekan dalam mesin.
Jika mereka sama, kembalikan solusi yang disandikan.
Lain, lakukan pencarian brute-force.

chazisop
sumber

-1

$O(1)$

umar
sumber

1

Saya tidak berpikir itu dianggap sebagai algoritma yang benar untuk masalah ini. Namun, algoritma Anda dapat dimodifikasi sehingga terlebih dahulu memeriksa apakah input sama dengan instance tertentu yang telah Anda tentukan sebelumnya (dalam O (1) waktu). Jika ya, itu akan menghasilkan jawaban yang sudah dikomputasi. Jika tidak, Anda memecahkan contoh yang diberikan dengan cara apa pun. Memikirkan hal itu, setiap algoritma yang benar berjalan dalam waktu O (1) untuk setiap instance, jika kita dapat mengambil konstanta yang berbeda di belakang notasi-O untuk instance yang berbeda. Itu sebabnya "kompleksitas kasus terbaik" dalam arti literal tidak berguna.

Tsuyoshi Ito

Jika Anda berbicara tentang perhitungan deterministik, non-probabilistik, akan butuh waktu linier (O (n)) untuk memeriksa apakah dua penyandian instance sama: memindai n bit dari penyandian input dan memverifikasi bahwa itu sama sebagai pengkodean yang diprogram, bukan?

Daniel Apon

2

@Aniel: Ya, tetapi jika salah satu instance diperbaiki, hanya membutuhkan waktu yang konstan, di mana konstanta tergantung pada panjang instance tetap.

Tsuyoshi Ito

Kelas Kompleksitas untuk Kasus Selain "Kasus Terburuk"

Jawaban: