Savitch teoremi

Bu maddenin veya maddenin bir bölümünün gelişebilmesi için konuda uzman kişilere gereksinim duyulmaktadır. Ayrıntılar için maddenin tartışma sayfasına lütfen bakınız. Konu hakkında uzman birini bulmaya yardımcı olarak ya da maddeye gerekli bilgileri ekleyerek Vikipedi'ye katkıda bulunabilirsiniz.

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, $f(n)$ uzay kullanan bir belirlenimsiz turing makinesi (nondeterministic turing machine $NTM$), belirlenimli bir turing makinesine (deterministic turing machine $TM$) dönüştürülürken $f(n)^2$ uzay gerektirir.

Teorem

Herhangi bir $f: N \to R^+$ fonksiyonu için, $f(n)\ge n$ gereksinimi karşılamak koşuluyla,
$NSPACE(f(n))\subseteq SPACE(f(n))$ dir.

İspat Fikri

$f(n)$ uzay kullanan bir $NTM$ simule ederken, akla ilk gelen yol $NTM$'nin tüm kollarını tek tek hesaplayarak, işlemi ilerletmektir. Bu yolu kullanırken, işlenen kola ait bilgilerin tutulması gerekmektedir. $f(n)$ uzay kullanan bir kol, en kötü ihtimalle $2^{O (f(n))}$ adımda, hesaplanabilir. Bütün kolların sırayla hesaplanması ise, hepsinin kayıt altında tutulması manasına gelir ki bu $2^{O (f(n))}$ uzay gerektirir. Üssel bir ilişki kuran bu yöntem, Savicth 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. $c_1$'i başlangıç, $c_2$'yi kabul konfigurasyonu ve t'yi $NTM$'nin kullanabileceği maksimum adım sayısı olarak kabul edersek, yieldability probleminin çözümü, $NTM$'nin verilen katarı kabul edip etmediğine karar verebilir.

Yieldability Problemi

Yinelemeli bir algoritima mantığıyla çözülebilecek olan yieldability problemin çözümünde aşağıdaki algoritma kullanılır.
CANYIELD($c_1,c_2,t$) #$c_1 ve c_2$ başlangıç ve kabul konfigurasyonları, $t$ adım sayısı


• 1. Eğer $t=1$ ise $c_1=c_2$ olup olmadığına veya $c_1$ den $c_2$ ye tek bir adımda geçip geçmediğine bakılır. Eğer ikisinden birisi doğru ise, kabul ikisi de yanlış ise ret döner

• 2. Eğer $t>1$ ise bütün $f(n)$ uzay kullanan ara konfigurasyonlar($c_m$) için:

• 3. CANYIELD($c_1 , c_m , t/2$) çağır

• 4. CANYIELD($c_m , c_2 , t/2$) çağır

• 5. Eğer 3. ve 4. adım kabulse, kabul et

• 6. Eğer kabul değilse ret dön

İspat

$N$ makinesi $f(n)$ uzayda $A$ diline karar veren bir $NTM$ olsun. $A$ diline karar veren bir belirlenimli $TM$ $M$ makinesi oluşturalım. $M$ makinesi, $N$ makinesinin herhangi bir konfigurasyonunun belirli adımda çözülüp çözülmediğini test etmek için yukarıda bahsediler CANYIELD algortimasını kullanır.
$w$ katarı $N$ makinesi için bir girdi katarı olsun.$w$ katarı üzerinde $c_1$ ve $c_2$ konfigurasyonları için, $N$ makinesi $c_1$ den $c_2$ ye $t$ veya daha az adımda geliyorsa, CANYIELD algoritması kabul döner, değilse ret döner.
Şimdi de $N$ makinesini simule eden bir $M$ makinesi oluşturalım:

$M$($w$)

• 1. CANYIELD($c_1$ , $c_2$ , $2^{f(n)}$) sonucu çıktı olarak döner.

CANYIELD algoritması kendisini yinelemeli olarak çağırdığında, mevcut durumu; $c_1$ ve $c_2$ değerlerini tutmak zorunda kalır. Öyleyse herbir yineleme adımında, ekstra $O(f(n))$ uzay gereklidir. Ayrıca, herbir yineleme adımında, $t$ adım yarıya düştüğünden, toplamda, $log_{2}2^{f(n)}=f(n)$ uzay gereklidir. O zaman bütün simule için gerekli olan uzay, $f(n)f(n)= f(n)^2$ olur. Bu da Savitch'in iddia ettiği gibi $O(f(n)^2)$ uzayda, bir $O(f(n))$ uzay $NTM$ bir $TM$ e dönüştürülebilir.

Dış bağlantılar

• Lance Fortnow, Foundations of Complexity, Lesson 18: Savitch's Theorem