İndirgenebilirlik ve Çözülemezlik Dereceleri
İndirgenebilirlik, bir problemi diğerine dönüştürerek problemlerin zorluk derecelerini karşılaştırmaktadır; eşit zorluktaki problemlerin gruplandırılması ise hesaplanabilirliğin ötesindeki dünyayı yapılandıran çözülemezlik derecelerini ortaya koymaktadır.
Tanım
Bir problem, ikincisi için bir çözücüye erişimi olan bir algoritma aracılığıyla ilkini çözebildiğinde diğerine indirgenmektedir; birbirine indirgenen problemler bir çözülemezlik derecesini paylaşmakta ve bu dereceler, göreceli algoritmik zorluğu ölçen bir sıralama oluşturmaktadır.
Kapsam
Bu konu, birebir ve Turing indirgenebilirliğini, indirgemelerin çözülemezliği kanıtlamak için kullanımını, kesinlikle daha zor problemler üreten Turing sıçrama (Turing jump) operasyonunu, problemleri mantıksal karmaşıklığa göre sınıflandıran aritmetik hiyerarşiyi ve ara derecelerin varlığı gibi derece kuramının (degree theory) merkezi sonuçlarını kapsamaktadır.
Temel sorular
- Bir çözülemez problemin diğerinden daha zor olduğunu nasıl söyleyebiliriz?
- İndirgemeler hem çözülemezliği kanıtlamak hem de problemleri düzenlemek için nasıl kullanılmaktadır?
- Turing sıçraması ne üretmektedir ve neden her zaman kesinlikle daha zordur?
- Karar verilebilir (decidable) problemler ile durma problemi (halting problem) arasında kesinlikle yer alan problemler var mıdır?
Temel kuramlar
- İndirgenebilirlik ve Turing sıçraması
- Turing indirgenebilirliği, problemleri oracle hesaplaması (oracle computation) aracılığıyla ilişkilendirmektedir ve bir problemin sıçraması (jump), ona göre durmayı (halting) kodlayarak her zaman kesinlikle daha zor olmakta, giderek daha zor problemlerden oluşan sonsuz bir kule oluşturmaktadır.
- Ara derecelerin varlığı
- Friedberg–Muchnik teoremi, öncelik yöntemini (priority method) kullanarak çözülemez ancak durma probleminden (halting problem) kesinlikle daha kolay olan hesaplanabilir sayılabilir problemler (computably enumerable problems) inşa ederek Post'un problemini çözmüş ve derecelerin zengin bir yapıya sahip olduğunu göstermiştir.
Klinik önem
İndirgeme tekniği, problemlerin çözülemez olduğunu veya karmaşıklık kuramında (complexity theory) çözülemez (intractable) olduğunu kanıtlamak için günlük olarak kullanılan temel bir yöntemdir: bilinen zor bir problemin yeni bir probleme indirgendiğini göstermek, zorluğu aktarmaktadır; çözülemezlik ve NP-tamlık (NP-completeness) sonuçları matematik ve bilgisayar bilimleri genelinde tam da bu şekilde ortaya konmaktadır.
Tarihçe
Turing, 1939'da oracle makinelerini tanıtmış, Post ise 1944'te çözülemezlik dereceleri çalışmasını çerçevelemiş ve ara hesaplanabilir sayılabilir derecelerin (intermediate computably enumerable degrees) var olup olmadığı sorununu ortaya atmıştır. Friedberg ve Muchnik, 1956–1957 yıllarında öncelik yöntemini (priority method) icat ederek bu sorunu bağımsız olarak çözmüş ve bu yöntem konunun merkezi bir tekniği haline gelmiştir.
Öne çıkan isimler
- Emil Post
- Alan Turing
- Richard Friedberg
- Albert Muchnik
İlgili konular
Temel eserler
- soare2016
- rogers1987
Sıkça sorulan sorular
- Sezgisel olarak bir indirgeme nedir?
- Bir problemi, başka bir problem için bir çözücü kullanarak çözme yöntemidir. Eğer A problemi için herhangi bir örneği B problemi için bir örneğe dönüştürebilir ve cevapların eşleşmesini sağlayabilirseniz, o zaman B en az A kadar zordur ve B'ye bir çözüm, A'ya bir çözüm sağlamaktadır.
- Durma probleminden daha zor problemler var mıdır?
- Evet, sonsuz sayıda vardır. Turing sıçramasını (Turing jump) durma problemine uygulamak, kesinlikle daha zor bir problem üretmekte ve bu işlemi tekrarlamak sonsuz bir hiyerarşi oluşturmaktadır; dolayısıyla çözülemezlik, tek bir seviye yerine sınırsız derecelerde ortaya çıkmaktadır.