Hesaplamalı Karmaşıklık Kuramı
Hesaplamalı karmaşıklık kuramı, herhangi bir algoritmanın problemleri çözmek için ihtiyaç duyduğu zaman, bellek ve diğer kaynak miktarına göre problemleri sınıflandırmaktadır. Bu sınıflandırma, verimli bir şekilde çözülebilen problemler ile çözülmesi imkansız görünen problemler arasında net sınırlar çizmektedir.
Tanım
Hesaplamalı karmaşıklık kuramı, hesaplamalı problemlerin Turing makinesi gibi bir model üzerinde çözülmesi için gereken kaynaklar, özellikle çalışma süresi ve bellek ile ölçülen içsel zorluğunu incelemektedir. Bu inceleme sonucunda problemleri karmaşıklık sınıflarına ayırmaktadır.
Kapsam
Bu kapsam, P, NP, PSPACE gibi zaman ve uzay karmaşıklık sınıflarını, polinom hiyerarşisini, NP-tamlık kuramını ve polinom zamanlı indirgemeleri, merkezi P ile NP sorusunu ve rastgelelik, etkileşim ve kanıtları içeren kaynak sınırlı modelleri ele almaktadır. Ayrıca, bu sınıfları ilişkilendiren hiyerarşi ve zorluk sonuçları da bu alana dahildir.
Alt konular
Temel sorular
- Belirli bir problemi çözmek doğası gereği ne kadar zaman ve bellek gerektirmektedir?
- Hangi problemler verimli bir şekilde çözülebilmekte ve hangileri tüm verimli algoritmalara direnmektedir?
- Problemlerin bir karmaşıklık sınıfının en zor üyeleri kadar zor olduğu nasıl gösterilmektedir?
- Rastgelelik, etkileşim veya belirlenimsizlik gerçek bir hesaplama gücü eklemekte midir?
Temel kuramlar
- Zaman ve uzay hiyerarşi teoremleri
- Kesinlikle daha fazla zaman veya uzay verildiğinde, makineler kesinlikle daha fazla problem çözebilmektedir. Bu durum, karmaşıklık sınıflarının gerçek hiyerarşiler oluşturduğunu ve bazı problemlerin doğası gereği diğerlerinden daha zor olduğunu kanıtlamaktadır.
- NP-tamlık
- Cook–Levin teoremi, her diğer NP probleminin indirgenebildiği NP problemlerini tanımlamaktadır. Bu nedenle, bunlardan herhangi biri için tek bir verimli algoritma, hepsini verimli bir şekilde çözebilecektir.
- Kaynak sınırlı modeller
- Rastgelelik, etkileşim veya dönüşümlülük eklemek, BPP, IP ve polinom hiyerarşisi gibi sınıfları tanımlamaktadır. Bu sınıfların ilişkileri, ek kaynakların neler sağlayabileceği ve sağlayamayacağı konusundaki tabloyu netleştirmektedir.
Klinik önem
Karmaşıklık kuramı, hangi problemlerin verimli algoritmalara izin verdiğini ve hangilerinin NP-zor olduğunu, dolayısıyla sezgisel yöntemler veya yaklaşıklık ile en iyi şekilde ele alınabileceğini belirleyerek uygulamaya rehberlik etmektedir. Belirli problemlerin varsayılan zorluğu, güvenliği hesaplamalı olarak imkansız olduğuna inanılan görevlere dayanan modern kriptografinin de temelini oluşturmaktadır.
Tarihçe
Hartmanis ve Stearns, 1965 yılında karmaşıklık sınıflarını tanımlayarak ve hiyerarşi teoremlerini kanıtlayarak bu alanı kurmuşlardır. Cook ve Levin, 1971 civarında NP-tamlığı tanıtmış, Karp ise 1972'de birçok doğal problemin tam olduğunu göstermiştir. Sonraki on yıllar ise rastgele, etkileşimli ve olasılıksal olarak kontrol edilebilir kanıt modellerini eklemiştir.
Öne çıkan isimler
- Stephen Cook
- Richard Karp
- Leonid Levin
- Juris Hartmanis
İlgili konular
Temel eserler
- cook1971
- hartmanisStearns1965
- aroraBarak2009
Sıkça sorulan sorular
- Hesaplanabilirlik ve karmaşıklık arasındaki fark nedir?
- Hesaplanabilirlik, bir problemin maliyetini göz ardı ederek herhangi bir algoritma ile çözülüp çözülemeyeceğini sormaktadır. Karmaşıklık ise problemin çözülebilir olduğunu varsaymakta ve bu çözümün zaman ve bellek açısından ne kadar maliyetli olması gerektiğini sorarak, prensipte çözülebilir olan problemler arasında daha ince ayrımlar yapmaktadır.
- NP-tamlık pratikte neden önemlidir?
- Bir problem NP-tam olarak gösterildiğinde, onlarca yıllık çabalara rağmen verimli bir algoritması bilinmeyen binlerce başka problemle ilişkilendirilmektedir. Bu durum, hızlı ve kesin bir algoritma arayışının muhtemelen boşuna olduğunu ve yaklaşıklık, sezgisel yöntemler veya özel durum metotlarının gerçekçi bir yol olduğunu işaret etmektedir.