Öncelikle neden bu başlığı açmam gerektiğinden bahsedeyim. Hesapsal karmaşıklık kuramı için yazdığım yazıda çok büyük bir hata yaptım. (bkz: #110899) Reklamın iyisi kötüsü olmaz.^:swh^ yaptığım hatayı yazının sonunda açıkladım. Ama burada da açıklamak istiyorum. Çünkü yaptığım şeyin hata olmasının sebebinin savitch’s theorem ile doğrudan ilgisi var. O yazıda birçok defa nondeterministic turing makinesi’nin deterministic turing makinesinden daha güçlü olduğunu doğrudan ifade eden veya ima eden ifadeler kullandım. Bu bilimsel anlamda yanlış bir ifade. Fakat sezgisel anlamda doğruluk payı var diyebiliriz. Fakat birkaç yerde ntm’lerin polinom zamanda çözdüğü problemleri dtm’lerin polinom zamanda çözemeyeceği anlamına gelecek ifadeler kullanmıştım. Bu affedilemeyecek derecede önemli bir yanlış olduğu için bu ifadeleri değiştirdim ama “güçlü” ifadelerine dokunmadım . Çünkü ntmler problemleri genelde dtmlerden daha hızlı (bilgisayar bilimcileri buna “effective” derler) çözüyor fakat teoride bütün turing makineleri eşit güçtedir.

O yazıda sadece zaman karmaşıklığı (time complexity) sınıflarını açıkladım fakat bir de uzay karmaşıklığı (space complexity) kavramı var. Uzay karmaşıklığı kavramı adından anlaşılacağı üzere bir problemi çözerken uzayın ne kadarını kullandığınızla ilgilenir. Yine üst seviye ama bilgisayar diliyle bir tanım yapacak olursak, uzay karmaşıklığı bir problemi çözerken bilgisayarın hafızasının ne kadarını kullandığınızla ilgilenir. Ntm ve dtm modelleri uzay-zaman karmaşıklığı açısından eşit güçtedir. Bu noktada yine o yazıda bahsetmediğim pspace ve npspace sınıflarından bahsetmem gerekiyor.

Pspace sınıfı, uzay-zaman karmaşıklığı açısından deterministic turing machine tarafından polinom zamanda çözülebilen problemler kümesini ifade eder.

Npspace sınıfı, uzay-zaman karmaşıklığı açısından nondeterministic turing machine tarafından polinom zamanda çözülebilen problemler kümesini ifade eder.

Yukarıda dedik ki ntm ve dtm modelleri uzay-zaman karmaşıklığı açısından eşit güçtedir. Dolayısıyla pspace=npsace doğrudur. Yani pspace=npspace sınıfı p ve np sınıflarını kapsayan bir kümedir. Savitch's theorem tam olarak bunu ifade eder. Bu da büyük resim. Karmaşıklık teorisi için yazdığım yazının son kısmında ntm’nin ve dtm’nin eşit güçte olmasının neden p=np’nin doğru olduğu anlamına gelmediğini bu başlıkta açıkladığımı da belirttim. artık huzur içinde uyuyabilirim.^:swh^