O tym, że problem TExtendedQBF jest PSPACE trudny, łatwo się przekonać - każda formuła w QBF jest przecież także formułą ExtendedQBF. Pozostaje jedynie dowieść, że TExtendedQBF jest w PSPACE.
Zwykłego QBF rozwiązywało się tak: (wiki)
Formułę Q_1x_1 Q_2x_2 Q_3x_3 .. Q_nx_n \phi(x_1,x_2,x_3,…x_n)
możemy zamienić na formuły:
A = Q_2 x_2 .. Q_n x_n \phi(0,x_2,x_3,..x_n)
B = Q_2 x_2 .. Q_n x_n \phi(1,x_2,x_3,..x_n)
Wtedy jeśli Q był kwantyfikatorem \exists to zwracaliśmy A \vee B, a jeśli „dla każdego”, to zwracaliśmy A \wedge B.
Teraz mamy jeszcze trzeci kwantyfikator - istnieje dokładnie jeden - musimy dla niego zwrócić A xor B. Tak zmodyfikowany algorytm powinien rozwiązywać rozszerzoną wersję problemu.