16:00 the professor seemed to explain the recursion as breadth-first process, but it actually should be depth-first process. If uses the breadth-first method, words do have to be remembered to start the next level. (one of the question later in the lecture asked the same thing)
1:07:17 I feel the real reason that a proof similar to Savitch's theorem is not working for proving TQBF to be PSPACE complete is not because the memory size is exponential, because you can used the same argument as the proof in Savitch's theorem that depth first process can reuse memory and reduce the size to polynomial. It is because the time in the reduction will be exponential. Or to say it in the other way, now either the memory size is exponential or the reduction time is exponential. So you need some PSPACE programs to hind the exponential reduction time in them (recall that a PSPACE program can have exponential run time). That is where TQBF come to the rescue, so the key is to understand the representation power of TQBF. With the key TQBF equation, Phi_{c1, c2,t} = E_m1 A_(c3, c4) \in {(c1, m1),(m1,c2)} [Phi_{c3,c4,t/2}], we can extend to next level as, Phi_{c1, c2,t} = E_m1 A_(c3, c4) \in {(c1, m1),(m1,c2)} [ E_m2 A_(c5, c6) \in {(c3, m2),(m2,c4)} [Phi_{c5,c6,t/4}] ] Continue with the same extension, now we can see why the whole program can be represented in one line with TQBF of size O(n^k)*O(n^k), which is maxima recursive depth times the size of one level in the recursive program.
16:00 the professor seemed to explain the recursion as breadth-first process, but it actually should be depth-first process. If uses the breadth-first method, words do have to be remembered to start the next level. (one of the question later in the lecture asked the same thing)
What a pleasure to see that there is free courses right after I ended Sipser's book !
Thanks for the upload.
The proof contents of the previous lecture and this lecture is breathtakingly amazing!
1:07:17 I feel the real reason that a proof similar to Savitch's theorem is not working for proving TQBF to be PSPACE complete is not because the memory size is exponential, because you can used the same argument as the proof in Savitch's theorem that depth first process can reuse memory and reduce the size to polynomial. It is because the time in the reduction will be exponential. Or to say it in the other way, now either the memory size is exponential or the reduction time is exponential. So you need some PSPACE programs to hind the exponential reduction time in them (recall that a PSPACE program can have exponential run time). That is where TQBF come to the rescue, so the key is to understand the representation power of TQBF.
With the key TQBF equation, Phi_{c1, c2,t} = E_m1 A_(c3, c4) \in {(c1, m1),(m1,c2)} [Phi_{c3,c4,t/2}], we can extend to next level as,
Phi_{c1, c2,t} = E_m1 A_(c3, c4) \in {(c1, m1),(m1,c2)} [ E_m2 A_(c5, c6) \in {(c3, m2),(m2,c4)} [Phi_{c5,c6,t/4}] ]
Continue with the same extension, now we can see why the whole program can be represented in one line with TQBF of size O(n^k)*O(n^k), which is maxima recursive depth times the size of one level in the recursive program.
1:12:03 So if I understood this correctly, the solution is to use iteration, not recursion 😅
What's on the horizon? Exclusive interview with Binance's CEO reveals future insights