Kelas Kompleksitas Waktu dan Ruang

Kelas kompleksitas mengelompokkan masalah keputusan berdasarkan waktu atau memori yang dibutuhkan mesin untuk menyelesaikannya, mengorganisir komputasi ke dalam lanskap terstruktur dari ruang logaritmik hingga waktu eksponensial.

Definition

Kelas kompleksitas adalah himpunan masalah yang dapat diselesaikan dalam batas sumber daya yang ditetapkan, biasanya waktu atau memori kerja yang digunakan oleh mesin Turing sebagai fungsi dari panjang masukan, dengan varian deterministik dan nondeterministik untuk setiap sumber daya.

Scope

Topik ini mencakup definisi kelas waktu dan ruang deterministik dan nondeterministik seperti P, NP, L, NL, PSPACE, dan EXPTIME, teorema hierarki yang memisahkannya, inklusi dan hubungan yang diketahui di antara mereka, teorema Savitch yang menghubungkan ruang nondeterministik dan deterministik, serta masalah lengkap yang mencirikan setiap kelas.

Core questions

• Bagaimana masalah dikelompokkan berdasarkan waktu dan memori yang dibutuhkan solusinya?
• Inklusi mana di antara kelas kompleksitas standar yang diketahui ketat?
• Bagaimana ruang nondeterministik berhubungan dengan ruang deterministik?
• Peran apa yang dimainkan oleh masalah lengkap dalam mencirikan suatu kelas?

Key theories

Teorema hierarki

Dengan waktu atau ruang asimtotik yang lebih banyak, sebuah mesin dapat memutuskan bahasa yang secara ketat lebih banyak, sehingga kelas waktu dan ruang membentuk hierarki yang tepat dan sumber daya tidak dapat disia-siakan tanpa kehilangan masalah.

Teorema Savitch

Setiap masalah yang dapat diselesaikan dalam ruang nondeterministik dapat diselesaikan secara deterministik hanya dengan menggunakan kuadrat dari ruang tersebut, sehingga untuk memori, tidak seperti yang tampaknya untuk waktu, nondeterminisme memberikan paling banyak keuntungan yang sederhana.

Clinical relevance

Penempatan masalah dalam kelas kompleksitas memberi tahu praktisi apa yang diharapkan: masalah dalam P dapat diskalakan ke masukan besar, masalah PSPACE-lengkap seperti banyak permainan dan tugas perencanaan menolak solusi yang efisien, dan struktur kelas memandu apakah akan mencari algoritma yang tepat, perkiraan, atau mendesain ulang masalah.

History

Hartmanis dan Stearns mendefinisikan kelas-kelas terbatas waktu dan membuktikan teorema hierarki waktu pada tahun 1965, mendirikan bidang ini. Kompleksitas ruang dikembangkan secara paralel, dengan teorema Savitch tahun 1970 dan hasil-hasil selanjutnya seperti penutupan ruang nondeterministik di bawah komplemen oleh Immerman dan Szelepcsényi yang menyempurnakan gambaran tersebut.

Key figures

• Juris Hartmanis
• Richard Stearns
• Walter Savitch
• Stephen Cook

Seminal works

• hartmanisStearns1965
• savitch1970

Frequently asked questions

Apa perbedaan antara kompleksitas waktu dan ruang?

Kompleksitas waktu menghitung jumlah langkah yang diambil algoritma, sedangkan kompleksitas ruang mengukur memori kerja yang digunakannya. Keduanya berperilaku berbeda: ruang dapat digunakan kembali saat komputasi berlangsung, itulah sebabnya ruang nondeterministik jauh kurang kuat relatif terhadap ruang deterministik daripada perbandingan analog untuk waktu yang tampaknya terjadi.

Mengapa teorema hierarki penting?

Teorema ini membuktikan bahwa lebih banyak sumber daya benar-benar memungkinkan lebih banyak masalah untuk diselesaikan, menyingkirkan kemungkinan bahwa semua kelas runtuh menjadi satu. Ini menjamin, misalnya, bahwa ada masalah yang dapat diselesaikan dalam waktu eksponensial tetapi tidak dalam waktu polinomial, yang menjadi dasar seluruh bangunan kelas kompleksitas.