Redusibilitas dan Derajat Ketakterpecahkan

Redusibilitas membandingkan kesulitan masalah dengan mengubah satu masalah menjadi masalah lain, dan pengelompokan masalah dengan tingkat kesulitan yang sama menghasilkan derajat ketakterpecahkan yang menyusun dunia di luar komputasi.

Definition

Suatu masalah direduksi menjadi masalah lain ketika sebuah algoritma dengan akses ke pemecah untuk masalah kedua dapat memecahkan masalah pertama; masalah-masalah yang saling mereduksi memiliki derajat ketakterpecahkan yang sama, dan derajat-derajat ini membentuk urutan yang mengukur kesulitan algoritmik relatif.

Scope

Topik ini mencakup redusibilitas banyak-satu dan Turing, penggunaan reduksi untuk membuktikan ketakterputusan (undecidability), operasi lompatan Turing (Turing jump) yang menghasilkan masalah yang secara signifikan lebih sulit, hierarki aritmetika yang mengklasifikasikan masalah berdasarkan kompleksitas logis, dan hasil-hasil sentral teori derajat seperti keberadaan derajat antara.

Core questions

• Bagaimana kita bisa mengatakan satu masalah yang tidak dapat dipecahkan lebih sulit daripada yang lain?
• Bagaimana reduksi digunakan baik untuk membuktikan ketakterputusan maupun untuk mengorganisir masalah?
• Apa yang dihasilkan oleh lompatan Turing, dan mengapa selalu secara signifikan lebih sulit?
• Apakah ada masalah yang secara ketat berada di antara yang dapat diputuskan dan masalah penghentian?

Key theories

Redusibilitas dan lompatan Turing

Redusibilitas Turing menghubungkan masalah melalui komputasi oracle, dan lompatan suatu masalah, yang mengkodekan penghentian relatif terhadapnya, selalu secara signifikan lebih sulit, menghasilkan menara masalah yang semakin sulit tanpa henti.

Keberadaan derajat antara

Teorema Friedberg–Muchnik memecahkan masalah Post dengan membangun masalah-masalah yang dapat dihitung secara enumerasi yang tidak dapat diputuskan namun secara ketat lebih mudah daripada masalah penghentian, menggunakan metode prioritas, menunjukkan bahwa derajat-derajat tersebut memiliki struktur yang kaya.

Clinical relevance

Teknik reduksi adalah metode yang umum digunakan untuk membuktikan masalah tidak dapat dipecahkan atau, dalam teori kompleksitas, tidak dapat ditangani (intractable): menunjukkan bahwa masalah sulit yang diketahui dapat direduksi menjadi masalah baru akan memindahkan kesulitan tersebut, yang merupakan cara bagaimana hasil ketakterputusan dan NP-kelengkapan ditetapkan di seluruh matematika dan ilmu komputer.

History

Turing memperkenalkan mesin oracle pada tahun 1939, dan Post pada tahun 1944 membingkai studi tentang derajat ketakterpecahkan dan mengajukan masalah apakah derajat komputasi enumerasi antara itu ada. Friedberg dan Muchnik secara independen memecahkannya pada tahun 1956–1957 dengan menemukan metode prioritas, yang menjadi teknik sentral dalam subjek tersebut.

Key figures

• Emil Post
• Alan Turing
• Richard Friedberg
• Albert Muchnik

Seminal works

• soare2016
• rogers1987

Frequently asked questions

Apa itu reduksi, secara intuitif?

Ini adalah cara memecahkan satu masalah menggunakan pemecah untuk masalah lain. Jika Anda dapat menerjemahkan setiap instans masalah A ke dalam instans masalah B sehingga jawabannya cocok, maka B setidaknya sama sulitnya dengan A, dan solusi untuk B menghasilkan solusi untuk A.

Apakah ada masalah yang lebih sulit daripada masalah penghentian?

Ya, tak terhingga banyaknya. Menerapkan lompatan Turing ke masalah penghentian menghasilkan masalah yang secara signifikan lebih sulit, dan mengulangi operasi tersebut membangun hierarki tanpa akhir, sehingga ketakterpecahkan datang dalam derajat yang tidak terbatas daripada satu tingkat saja.