TQBF Problemi
Çözüm

TQBF i belirleyen bir polinomsal yer algoritması oluşturacağız.
T=  verisini kullanan bir tamamen belirlenmiş boolean formül.
Q hiç belirleyici içemiyorsa, bu durumda Q sadece sabitlerden oluşur. Q yu işleriz eğer doğruysa kabul et. Yoksa reddet.
Eğer  Q=\exists xG ye eşitse, tekrarlarla T yi G üzerinde çalıştır. Önce x değişkeni yerine 0 koy, daha sonra da x değişkeni yerine 1 koy. Eğer iki sonuçtan biri doğruysa kabul et yoksa reddet.
Eğer  Q=\forall xG ye eşitse, tekrarlarla T yi Q üzerinde çağır. Önce x değişkeni için 0 koy sonra 1 koy. Eğer iki sonuçta doğruysa kabul et yoksa reddet.
T algoritması TQBF i belirler.
Bu algoritmanın yer karmaşıklığını analiz ettiğimizde şunu gözlemleriz: Formül, içerisindeki değişken sayısı kadar çağrılır. Her seviyede sadece bir değişken değerini tutarız. Bu yüzden toplam kullanılacak yer  O(m), m = toplam değişken sayısı, dır. Buradan T nin Lineer zamanda bittiğini gözlemleriz.
A, M Turing Makinesi tarafından  n^{k} polinomsal yerde tanımlanan bir dil olsun. Şimdi A'dan TQBF e Polinomsal zaman indirgemeye çalışacağız. Bu indirgeme için bir 'w' kelimesi kullanılsın. Söyle ki; Q ancak, M makinası 'w' yi kabul ettiğinde doğru olsun.
Q yu nasıl oluşturacağımızı göstermek için daha genel bir problemi çözülür. c1 ve c2 iki tane değişken listesi olsun. ve t>0 olan bir sayı. Öncelikle Qc1,c2,t formülü kurarız. Eğer c1 ve c2 yi doğru bir şekilde kurarsak; formül, M makinası c1 den c2 ye en fazla t stepte giderse doğru olur. Bu durumda, Qcstart,caccept,h,  h=2^{d}f(n) alırız. Böylece M n verisi üzerinde en fazla  2^{d}f(n) değişik konfigürasyona sahip olur. Burada  f(n)=n^{k} ve t 2 nin katı olacak şekilde alalım.
Eğer t=1 ise, Qc1,c2,t kolayca oluşturulabilir. Böyle bir durumda, ya c1 c2 ye eşittir ya da c1 den c2 ye M makinasında bir step vardır.
Eğer t>1 ise, Qc1,c2,t formülü tekrarlarla kurulur. Şöyle ki:
Qc1,c2,t =  \exists m1[
Qc1,m1,t/2 \land Qm1,c2,t/2 ]
m1 bu arada M ye ait bir konfigurasyonu temsil eder.  \exists m1:  \exists  x1,......,xl in kısaca yazılmış halidir.  l=O(n^{k}) ve x1,.....,xl m1 yi kodlayan değişkenlerdir. 
Qc1,c2,t nin yaratılması şunu belirtir: M makinası c1 den c2 ye en fazla t stepte gider. Ve eğer m1 ara stepi varsa, şöyle ki M c1 den m1 e t/2 stepte gidsin ve m1 dan c2 e t/2 stepde gidsin. 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^{d}f(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 =  \exists m1  \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^{d}f(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^{d}f(n)),  O(f(n)) dır. Bu yüzden sonuç formülü: O f^{2}(n) dır.