Teori Kompleksitas Komputasi

Teori kompleksitas komputasi mengklasifikasikan masalah berdasarkan jumlah waktu, memori, dan sumber daya lain yang dibutuhkan algoritma untuk menyelesaikannya, menarik garis tegas antara apa yang dapat diselesaikan secara efisien dan apa yang tampaknya tidak dapat diatasi.

Definition

Teori kompleksitas komputasi mempelajari kesulitan intrinsik masalah komputasi yang diukur oleh sumber daya, terutama waktu berjalan dan memori, yang diperlukan untuk menyelesaikannya pada model seperti mesin Turing, dan mengelompokkan masalah ke dalam kelas kompleksitas yang sesuai.

Scope

Area ini mencakup kelas kompleksitas waktu dan ruang seperti P, NP, PSPACE, dan hierarki polinomial, teori NP-kelengkapan dan reduksi waktu polinomial, pertanyaan sentral P versus NP, dan model terikat sumber daya yang menggabungkan keacakan, interaksi, dan bukti, bersama dengan hierarki dan hasil kekerasan yang menghubungkan kelas-kelas ini.

Sub-topics

• NP-Completeness and Reductions
• Randomized and Interactive Computation
• The P versus NP Problem
• Time and Space Complexity Classes

Core questions

• Berapa banyak waktu dan memori yang secara inheren dibutuhkan untuk menyelesaikan masalah tertentu?
• Masalah mana yang dapat diselesaikan secara efisien dan mana yang tampaknya menolak semua algoritma yang efisien?
• Bagaimana masalah ditunjukkan sekeras anggota terberat dari kelas kompleksitas?
• Apakah keacakan, interaksi, atau nondeterminisme menambah kekuatan komputasi yang nyata?

Key theories

Teorema hierarki waktu dan ruang

Dengan waktu atau ruang yang secara ketat lebih banyak, mesin dapat menyelesaikan masalah yang secara ketat lebih banyak, membuktikan bahwa kelas kompleksitas membentuk hierarki yang asli dan bahwa beberapa masalah secara inheren lebih sulit daripada yang lain.

NP-kelengkapan

Teorema Cook–Levin mengidentifikasi masalah dalam NP yang kepadanya setiap masalah NP lainnya direduksi, sehingga satu algoritma efisien untuk salah satunya akan secara efisien menyelesaikan semuanya.

Model terikat sumber daya

Menambahkan keacakan, interaksi, atau alternasi mendefinisikan kelas-kelas seperti BPP, IP, dan hierarki polinomial, yang hubungannya mempertajam gambaran tentang apa yang dapat dan tidak dapat diperoleh oleh sumber daya tambahan.

Clinical relevance

Teori kompleksitas memandu praktik dengan mengesahkan masalah mana yang memungkinkan algoritma efisien dan mana yang NP-hard sehingga paling baik ditangani dengan heuristik atau pendekatan; kekerasan yang diasumsikan dari masalah tertentu juga mendasari kriptografi modern, yang keamanannya bergantung pada tugas-tugas yang diyakini tidak mungkin secara komputasi.

History

Hartmanis dan Stearns mendirikan bidang ini pada tahun 1965 dengan mendefinisikan kelas kompleksitas dan membuktikan teorema hierarki. Cook dan Levin memperkenalkan NP-kelengkapan sekitar tahun 1971, Karp menunjukkan banyak masalah alami yang lengkap pada tahun 1972, dan dekade-dekade berikutnya menambahkan model bukti acak, interaktif, dan yang dapat diperiksa secara probabilistik.

Key figures

• Stephen Cook
• Richard Karp
• Leonid Levin
• Juris Hartmanis

Seminal works

• cook1971
• hartmanisStearns1965
• aroraBarak2009

Frequently asked questions

Apa perbedaan antara komputabilitas dan kompleksitas?

Komputabilitas bertanya apakah suatu masalah dapat diselesaikan oleh algoritma apa pun sama sekali, mengabaikan biaya. Kompleksitas mengasumsikan masalah dapat dipecahkan dan bertanya seberapa mahal solusi itu dalam waktu dan memori, menarik perbedaan yang lebih halus di antara masalah-masalah yang pada prinsipnya dapat dipecahkan.

Mengapa NP-kelengkapan penting dalam praktik?

Ketika suatu masalah ditunjukkan NP-lengkap, itu terkait dengan ribuan masalah lain yang tidak diketahui algoritma efisiennya meskipun telah dilakukan upaya selama puluhan tahun. Ini menandakan bahwa mencari algoritma eksak yang cepat kemungkinan besar sia-sia dan bahwa pendekatan, heuristik, atau metode kasus khusus adalah jalur yang realistis.