TQBF Problemi: Revizyonlar arasındaki fark
| [kontrol edilmiş revizyon] | [kontrol edilmiş revizyon] |
İçerik silindi İçerik eklendi
Taşındı: Kategori:Karmaşıklık kuramı -> Kategori:Karmaşıklık teorisi (Katalitik) |
Değişiklik özeti yok |
||
52. satır:
Q<sub>c<sub>1</sub>,c<sub>2</sub>,t</sub> nin yaratılması şunu belirtir: M makinası c<sub>1</sub> den c<sub>2</sub> ye en fazla t stepte gider. Ve eğer m<sub>1</sub> ara stepi varsa, şöyle ki M c<sub>1</sub> den m<sub>1</sub> e t/2 stepte gidsin ve m<sub>1</sub> dan c<sub>2</sub> e t/2 stepde gidsin. Bu durumda, Q<sub>c<sub>1</sub>,m<sub>1</sub>,t/2</sub> ve Q<sub>m<sub>1</sub>,c<sub>2</sub>,t/2</sub> formülleri oluşturulabilir. Fakat bu şekilde genel formülü çıkarmaya kalkarsak, çıkacak formül çok uzun olur. Çünkü, her tekrarda biz formülü 2'ye bölüyoruz. Ve her step geçtikten sonra genel formül 2 ye katalanıyor. Başlangıçta t=<math>2^df(n)</math> aldığımız için exponential bir formül ortaya çıkar.
Formülün boyutunu kısaltmak için <math>\exists</math> in yanına
Q<sub>c<sub>1</sub>,c<sub>2</sub>,t</sub> = <math>\exists</math>m<sub>1</sub> <math>\forall</math> (c<sub>3</sub>,c<sub>4</sub>) <math>\in</math> {(c<sub>1</sub>,m<sub>1</sub>),(m<sub>1</sub>,c<sub>2</sub>)} [Q<sub>c<sub>3</sub>,c<sub>4</sub>,t/2</sub>]
| |||