Although I didn't watch the whole video, but I browsed your channel and saw tons of detailed videos about algorithms, which was impressive. Hope more people will discover your channel. Add oil.
Really nice video! Do you have any recommondations for sources on proofs showing SPACE(O(log log n)) = SPACE(O(1))? Really struggeling with the proof given in "Theory of Computation (2006)" by Dexter C. Kozen
I learned this from "Computational Complexity: A Conceptual Perspective" by Oded Goldreich. Whether that is easier to follow is probably a matter of personal preference. The concept of configurations (as briefly introduced here th-cam.com/video/ctxu6We41G4/w-d-xo.html) is important for this. Very roughly, if you have space o(log log n) then the number of configurations is also small. This then implies that the running time of the machine must be limited. In fact, it is so limited that the machine cannot even always read the entire input. But if it does not read the entire input, it is possible to trick the machine into producing incorrect outputs.
@@compscilessons Thank you for the fast reply. The video was really helpful since as you said the basics of the proof seem to come from PSPACE-completeness. I will give the book a read and hope I will be able to finally understand this proof even further. Yet again thanks alot!
Although I didn't watch the whole video, but I browsed your channel and saw tons of detailed videos about algorithms, which was impressive. Hope more people will discover your channel. Add oil.
Really nice video! Do you have any recommondations for sources on proofs showing SPACE(O(log log n)) = SPACE(O(1))? Really struggeling with the proof given in "Theory of Computation (2006)" by Dexter C. Kozen
I learned this from "Computational Complexity: A Conceptual Perspective" by Oded Goldreich. Whether that is easier to follow is probably a matter of personal preference.
The concept of configurations (as briefly introduced here th-cam.com/video/ctxu6We41G4/w-d-xo.html) is important for this. Very roughly, if you have space o(log log n) then the number of configurations is also small. This then implies that the running time of the machine must be limited. In fact, it is so limited that the machine cannot even always read the entire input. But if it does not read the entire input, it is possible to trick the machine into producing incorrect outputs.
@@compscilessons Thank you for the fast reply. The video was really helpful since as you said the basics of the proof seem to come from PSPACE-completeness. I will give the book a read and hope I will be able to finally understand this proof even further. Yet again thanks alot!