- Katılım
- 7 Eyl 2009
- Konular
- 6,986
- Mesajlar
- 38,038
- Çözüm
- 1
- Online süresi
- 7d 22h
- Reaksiyon Skoru
- 1,833
- Altın Konu
- 0
- Başarım Puanı
- 494
- MmoLira
- 6,600
- DevLira
- 0
HERAKLES Otomatik Avlı kalıcı sunucu. 19 Haziran'da açılıyor. Atius & Wizard güvencesiyle hemen kayıt ol, ön kayıt ödülleri aktif. HEMEN TIKLA!
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.[1]
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.
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.
