TQBF Problemi; Qc1,c4,t/2 hangi değerleri alır?
c3 ve c4 değişkenleri sırasıyla c1,m1 veya m1,c2 değerleri alabilir.
Bu durumda, Qc1,m1,t/2 ve Qm1,c2,t/2 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=2^df(n) aldığımız için exponential bir formül ortaya çıkar. Formülün boyutunu kısaltmak için \exists in yanına bir de \forall ekleriz. Şöyle ki: Qc1,c2,t = \existsm1 \forall (c3,c4) \in {(c1,m1), (m1,c2)} [Qc3,c4,t/2] Yeni değikenlerin eklenmesi, iki tekrarlayan formülü teke indirdi. \forall (c3,c4) \in {(c1,m1), (m1,c2)} ifadesiyle, c3 ve c4 değişkenleri sırasıyla c1,m1 veya m1,c2 değerleri alabilir. Ve Qc3,c4,t/2] her iki durumda da doğrudur. Qcstart,caccept,h, h=2^df(n) nin uzunluğunu hesaplarken şunu söyleyebiliriz: tekrarlayan her step genel formüle bir eleman ekler bu yüzden formülün tamamı lineer uzunluktadır. Toplam uzunluk ise:O(f(n)) dır. Tekrarlardaki step sayısı: log(2^df(n)), O(f(n)) dır. Bu yüzden sonuç formülü: Of^2(n) dır. .Karmaşıklık teorisindendir. Matematik teoremleri.