Apa yang mudah dilakukan komputer dan apa yang hampir mustahil? Pertanyaan-pertanyaan ini adalah inti dari masalah kompleksitas komputasi. Kami menyajikan Anda peta lanskap ini.
Kelas kompleksitas yang berbeda mengurutkan tugas dalam bentuk hierarkis. Satu kelas dapat berisi semua tugas yang lain, ditambah tugas yang membutuhkan sumber daya komputasi tambahan.Apa kesulitan mendasar dari tugas ini? Ini adalah rumusan tugas dasar para ilmuwan komputer yang sedang mencoba untuk menyortir tugas sesuai dengan yang disebut.
kelas kesulitan . Ini adalah grup yang berisi semua tugas komputasi yang membutuhkan tidak lebih dari jumlah sumber daya komputasi yang tetap - seperti waktu atau memori. Mari kita ambil contoh sederhana dengan angka besar seperti 123 456 789 001. Orang mungkin bertanya: apakah itu bilangan prima - yang membagi hanya dengan 1 dan itu sendiri? Ilmuwan komputer dapat menjawabnya dengan algoritma cepat - sedemikian rupa sehingga mereka tidak mulai melambat pada jumlah besar yang sewenang-wenang. Dalam kasus kami, ternyata angka ini tidak prima. Kemudian kita dapat mengajukan pertanyaan: apa faktor utamanya? Tetapi tidak ada algoritma cepat untuk menjawabnya - hanya jika Anda menggunakan komputer kuantum. Oleh karena itu, para ilmuwan komputer percaya bahwa dua tugas ini termasuk kelas kompleksitas yang berbeda.
Ada banyak kelas kesulitan yang berbeda, walaupun dalam kebanyakan kasus para peneliti tidak dapat membuktikan bahwa satu kelas jelas berbeda dari yang lain. Bukti perbedaan antar kelas adalah salah satu tugas paling sulit dan penting di bidang ini.
Perbedaan antara kelas hampir tidak dapat dibedakan atau jelas, dan cukup sulit untuk memahami semua kelas dengan baik. Oleh karena itu, kami telah menyusun panduan ini untuk tujuh kelas kesulitan paling mendasar. Dan ya, Anda tidak akan lagi membingungkan BPP dan BQP.
P
Melambangkan : waktu polinomial
Deskripsi singkat : semua tugas yang dapat diselesaikan dengan mudah oleh komputer klasik (non-kuantum).
Deskripsi yang tepat : algoritma kelas P harus berhenti bekerja dan memberikan jawaban yang benar tidak lebih dari waktu n
c , di mana n adalah panjang dari data input, c adalah konstanta.
Tugas Umum :
- Apakah bilangan prima?
- Apa jalur terpendek antara dua titik?
Apa yang ingin diketahui para peneliti : Apakah P bertepatan dengan NP? Kebetulan akan merevolusi ilmu komputer dan membuat sebagian besar sistem kriptografi menjadi tidak berarti (tetapi hampir tidak ada yang percaya ini).
NP
Melambangkan : waktu polinomial non-deterministik
Deskripsi singkat : semua tugas yang bisa diperiksa dengan mudah oleh komputer klasik jika ada solusinya.
Deskripsi persis : masalahnya jatuh ke NP kelas ketika, jika jawabannya adalah ya, ada bukti singkat tentang kebenaran jawaban. Jika inputnya adalah string X, dan Anda perlu memutuskan apakah jawabannya cocok dengan "ya", maka bukti singkat akan menjadi string lain, Y, yang dapat digunakan untuk memverifikasi jawaban yang benar "ya" dalam waktu polinomial. (Y kadang-kadang disebut "saksi singkat" - semua tugas dari NP memiliki saksi singkat, berkat itu mereka dapat diperiksa).
Tugas Umum :
- Tugas mengklik . Bayangkan grafik dengan tepi dan simpul - misalnya, simpul menunjukkan pengguna jaringan sosial, dan tepi menunjukkan bahwa mereka adalah "teman". Klik adalah bagian dari grafik ini di mana semua orang adalah teman satu sama lain. Anda dapat mengajukan pertanyaan berikut tentang grafik: apakah ada klik 20 orang di dalamnya? 50 orang? 100? Menemukan klik adalah tugas NP-lengkap , yaitu, kompleksitasnya adalah yang tertinggi dari semua tugas NP. Tetapi, memiliki jawaban potensial - subset 50 node yang mungkin atau mungkin bukan klik - mudah diverifikasi.
- Tugas salesman . Mengingat seperangkat kota dengan jarak antara dua pasangan - apakah ada cara untuk mengelilingi semua kota, mengemudi kurang dari jarak tertentu? Misalnya, dapatkah seorang salesman melakukan perjalanan ke semua ibukota AS dengan jarak kurang dari 11.000 mil?
Apa yang peneliti ingin ketahui: P = NP? Spesialis dalam ilmu komputer dan tidak mendekati untuk memecahkan masalah ini.
PH
Melambangkan : hierarki polinomial
Deskripsi Singkat : PH adalah generalisasi dari NP. Ini berisi semua tugas yang bisa diperoleh dengan memulai dengan tugas dari NP, dan memaksakan tingkat kesulitan tambahan.
Deskripsi yang tepat : PH berisi tugas-tugas dengan sejumlah "quantifiers" berbeda yang menyulitkan tugas-tugas ini. Contoh masalah dengan pembilang yang berbeda: Jika kita diberi X, apakah ada Y sedemikian rupa sehingga untuk setiap Z ada W yang R dipenuhi? Semakin banyak kuantifier dalam masalah, semakin rumit, dan semakin tinggi hierarki polinomial.
Tugas tipikal adalah menentukan apakah benar ada klik ukuran 50, dan tidak ada klik ukuran 51.
Apa yang ingin diketahui oleh para peneliti : belum ada yang dapat membuktikan bahwa PH berbeda dari P. Masalah ini setara dengan kesetaraan P dan NP, karena jika tiba-tiba ternyata P = NP, maka semua PH akan dikurangi menjadi P (P = PH).
PSPACE
Melambangkan : batasan ruang polinomial
Deskripsi singkat : PSPACE berisi semua tugas yang dapat diselesaikan menggunakan jumlah memori yang wajar.
Deskripsi persis : Saat menyelesaikan tugas PSPACE, Anda tidak lagi khawatir tentang waktu, Anda hanya khawatir tentang jumlah memori yang diperlukan agar algoritma berfungsi. Ilmuwan komputer telah membuktikan bahwa PSPACE mengandung PH yang mengandung NP yang mengandung P.
Tugas umum : semua tugas dari P, NP, dan PH terdapat di PSPACE.
Apa yang peneliti ingin ketahui : Apakah PSPACE berbeda dari P?
Bqp
Menunjukkan : waktu polinomial kuantum dengan batasan probabilitas kesalahan
Deskripsi singkat : semua tugas yang dapat dengan mudah diselesaikan di komputer kuantum.
Deskripsi persis : semua tugas yang dapat diselesaikan pada komputer kuantum dalam waktu polinomial.
Masalah umum : temukan faktor utama bilangan bulat.
Apa yang ingin diketahui oleh para peneliti : Sejauh ini, telah terbukti bahwa BQP terkandung dalam PSPACE dan bahwa BQP mengandung P. Para peneliti tidak tahu apakah BQP terkandung dalam NP, tetapi mereka percaya bahwa dua kelas ini tidak dapat dibandingkan - ada tugas yang merupakan bagian dari NP, tetapi tidak di BQP, dan sebaliknya.
KECUALI
Melambangkan : waktu eksponensial
Deskripsi singkat : semua tugas yang dapat diselesaikan dalam waktu eksponensial di komputer klasik.
Deskripsi persis : EXP berisi semua kelas sebelumnya - P, NP, PH, PSPACE, dan BQP. Peneliti membuktikan bahwa ini berbeda dari P - mereka menemukan tugas yang merupakan bagian dari EXP dan bukan bagian dari P.
Tugas khas : generalisasi permainan seperti catur dan catur. Jika papan catur dapat berukuran berapa saja, maka tugas menentukan apakah salah satu pemain memiliki keunggulan menjadi tugas EXP.
Apa yang ingin diketahui oleh para peneliti : mereka ingin membuktikan bahwa PSPACE tidak mengandung EXP. Mereka percaya bahwa ada tugas-tugas yang merupakan bagian dari EXP tetapi bukan bagian dari PSPACE, karena kadang-kadang dibutuhkan banyak waktu untuk menyelesaikan tugas dari EXP. Peneliti tahu bagaimana memisahkan EXP dan P.
BPP
Melambangkan : waktu polinomial dengan batasan probabilitas kesalahan
Deskripsi singkat : tugas yang dapat diselesaikan dengan cepat menggunakan algoritma yang menggunakan keacakan.
Deskripsi persis : BPP sama dengan P, dengan perbedaan bahwa algoritma dapat mencakup langkah-langkah pengambilan keputusan secara acak. Algoritma di BPP perlu memberikan jawaban yang benar dengan probabilitas mendekati 1.
Tugas umum : Anda memiliki dua rumus berbeda yang memberikan polinomial dengan banyak variabel. Apakah rumus-rumus ini menghitung polinomial yang sama? Ini adalah tugas untuk memeriksa identitas polinom.
Apa yang ingin diketahui para peneliti : Apakah BPP dan P. sama. Jika mereka sama, maka setiap algoritma dengan keacakan dapat dihilangkan dari keacakan. Mereka percaya itu adalah - bahwa untuk setiap masalah yang ada algoritma acak yang efektif, ada algoritma deterministik yang efektif - tetapi mereka belum dapat membuktikan ini.