Savitch teoremi

Savitch Teoremi, uzay karmaşıklığını konu edinen ve bu hususta sonuca varan en eski teoremlerden biridir. Belirlenimsiz makinelerin belirlenimli makinelere dönüştürülmesinde, gerekli olan uzay karmaşıklığını incelemiştir ve beklenenden çok daha küçük uzay gereksinimi olduğunu ortaya koymuştur. Daha formal bir ifadeyle,  uzay kullanan bir belirlenimsiz Turing makinesi (nondeterministic turing machine ), belirlenimli bir turing makinesine (deterministic turing machine ) dönüştürülürken  uzay gerektirir.Sipser 2006 Introduction to the Theory of Computation, Second

 Teorem 
Herhangi bir  fonksiyonu için,  gereksinimi karşılamak koşuluyla,  dir.

 İspat fikri 
 uzay kullanan bir  simule ederken, akla ilk gelen yol 'nin tüm kollarını tek tek hesaplayarak, işlemi ilerletmektir. Bu yolu kullanırken, işlenen kola ait bilgilerin tutulması gerekmektedir.  uzay kullanan bir kol, en kötü ihtimalle  adımda, hesaplanabilir. Bütün kolların sırayla hesaplanması ise, hepsinin kayıt altında tutulması manasına gelir ki bu  uzay gerektirir. Üssel bir ilişki kuran bu yöntem, Savitch teoreminin iddia ettiği uzaydan çok daha fazla uzay gerektirmiş olur.

Bunun yerine, çözümü yinelemeli bir algoritma olan, yieldability probleminin yöntemi uygulanmıştır. 'i başlangıç, 'yi kabul konfigurasyonu ve t'yi 'nin kullanabileceği maksimum adım sayısı olarak kabul edersek, yieldability probleminin çözümü, 'nin verilen katarı kabul edip etmediğine karar verebilir.

 Yieldability problemi 
Yinelemeli bir algoritma mantığıyla çözülebilecek olan yieldability probleminin çözümünde aşağıdaki algoritma kullanılır. 
CANYIELD() # başlangıç ve kabul konfigürasyonları,  adım sayısı
 1.  Eğer  ise  olup olmadığına veya 'den 'ye tek bir adımda geçip geçmediğine bakılır. Eğer ikisinden biri doğru ise kabul, ikisi de yanlış ise ret döner
 2. Eğer  ise bütün  uzay kullanan ara konfigürasyonlar() için:
 3. CANYIELD() çağır
 4. CANYIELD() çağır
 5. Eğer 3. ve 4. adım kabulse, kabul eder 
 6. Eğer kabul değilse ret döner

 İspat 
 makinesi  uzayda  diline karar veren bir  olsun.  diline karar veren bir belirlenimli    makinesi oluşturalım.  makinesi,  makinesinin herhangi bir konfigürasyonunun belirli adımda çözülüp çözülmediğini test etmek için yukarıda bahsedilen CANYIELD algortimasını kullanır. 
 katarı  makinesi için bir girdi katarı olsun. katarı üzerinde  ve  konfigürasyonları için,  makinesi 'den 'ye  veya daha az adımda geliyorsa, CANYIELD algoritması kabul döner, değilse ret döner.
Şimdi de  makinesini simüle eden bir  makinesi oluşturalım:

()
 1.  CANYIELD(, , ) sonucu çıktı olarak döner.

CANYIELD algoritması kendisini yinelemeli olarak çağırdığında, mevcut durumu;  ve  değerlerini tutmak zorunda kalır. Öyleyse her bir yineleme adımında, ekstra  uzay gereklidir. Ayrıca, her bir yineleme adımında,  adım yarıya düştüğünden, toplamda,  uzay gereklidir. O zaman bütün simüle için gerekli olan uzay,  olur. Bu da Savitch'in iddia ettiği gibi  uzayda, bir  uzay  bir 'e dönüştürülebilir.

 Kaynakça 

 Dış bağlantılar 
 Lance Fortnow, ''Foundations of Complexity, Lesson 18: Savitch's Theorem ()

Kategori:Matematik teoremleri