Zaman ve Uzay Karmaşıklık Sınıfları
Karmaşıklık sınıfları, karar problemlerini bir makinenin bunları çözmek için ihtiyaç duyduğu zaman veya belleğe göre gruplandırmakta, hesaplamayı logaritmik uzaydan üstel zamana kadar yapılandırılmış bir düzene sokmaktadır.
Tanım
Bir karmaşıklık sınıfı, bir kaynağın belirtilen bir sınırı dahilinde çözülebilen problemler kümesidir; bu kaynak genellikle bir Turing makinesi tarafından girdi uzunluğunun bir fonksiyonu olarak kullanılan zaman veya çalışma belleğidir ve her kaynak için deterministik ve nondeterministik varyantları bulunmaktadır.
Kapsam
Bu konu, P, NP, L, NL, PSPACE ve EXPTIME gibi deterministik ve nondeterministik zaman ve uzay sınıflarının tanımını, bunları ayıran hiyerarşi teoremlerini, aralarındaki içermeleri ve bilinen ilişkileri, nondeterministik ve deterministik uzayı ilişkilendiren Savitch teoremini ve her sınıfı karakterize eden tam problemleri kapsamaktadır.
Temel sorular
- Problemler, çözümlerinin gerektirdiği zaman ve belleğe göre nasıl gruplandırılmaktadır?
- Standart karmaşıklık sınıfları arasındaki hangi içermelerin kesin olduğu bilinmektedir?
- Nondeterministik uzay, deterministik uzayla nasıl ilişkilidir?
- Tam problemler, bir sınıfı karakterize etmede hangi rolü oynamaktadır?
Temel kuramlar
- Hiyerarşi teoremleri
- Asimptotik olarak daha fazla zaman veya uzay ile bir makine kesinlikle daha fazla dili kararlaştırabilmektedir; bu nedenle zaman ve uzay sınıfları uygun hiyerarşiler oluşturmakta ve problemler kaybedilmeden kaynaklar boşa harcanamamaktadır.
- Savitch teoremi
- Nondeterministik uzayda çözülebilen herhangi bir problem, o uzayın yalnızca karesi kullanılarak deterministik olarak çözülebilmektedir; bu nedenle, zamandan farklı olarak bellek için nondeterminizm en fazla mütevazı bir avantaj sağlamaktadır.
Klinik önem
Bir problemi bir karmaşıklık sınıfına yerleştirmek, uygulayıcılara ne beklemeleri gerektiğini bildirmektedir: P sınıfındaki problemler büyük girdilere ölçeklenebilirken, birçok oyun ve planlama görevi gibi PSPACE-tam problemler verimli çözümlere direnç göstermektedir ve sınıf yapısı, kesin algoritmalar, yaklaşımlar arayışına girilip girilmeyeceği veya problemin yeniden tasarlanıp tasarlanmayacağı konusunda yol göstermektedir.
Tarihçe
Hartmanis ve Stearns, 1965 yılında zaman sınırlı sınıfları tanımlamış ve zaman hiyerarşi teoremini kanıtlayarak bu alanı kurmuşlardır. Uzay karmaşıklığı paralel olarak geliştirilmiş olup, Savitch'in 1970 tarihli teoremi ve Immerman ile Szelepcsényi'nin nondeterministik uzayın tümleyen altında kapanışı gibi sonraki sonuçlar tabloyu netleştirmiştir.
Öne çıkan isimler
- Juris Hartmanis
- Richard Stearns
- Walter Savitch
- Stephen Cook
İlgili konular
Temel eserler
- hartmanisStearns1965
- savitch1970
Sıkça sorulan sorular
- Zaman ve uzay karmaşıklığı arasındaki fark nedir?
- Zaman karmaşıklığı, bir algoritmanın attığı adım sayısını sayarken, uzay karmaşıklığı kullandığı çalışma belleğini ölçmektedir. Bunlar farklı davranmaktadır: hesaplama ilerledikçe uzay yeniden kullanılabilmektedir, bu nedenle nondeterministik uzay, zaman için benzer karşılaştırmaya göre deterministik uzaya kıyasla çok daha az güçlü görünmektedir.
- Hiyerarşi teoremleri neden önemlidir?
- Daha fazla kaynağın gerçekten daha fazla problemin çözülmesine olanak tanıdığını kanıtlamakta, tüm sınıfların tek bir sınıfa çökme olasılığını ortadan kaldırmaktadırlar. Bu durum, örneğin, üstel zamanda çözülebilen ancak polinom zamanda çözülemeyen problemlerin varlığını garanti etmekte ve karmaşıklık sınıflarının tüm yapısını sağlamlaştırmaktadır.