Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are in the video description. Names are listed in alphabetical order by surname. Platinum: Micah Wood Silver: Simone Glinz, Josh Hibschman, Timmy Gy, Patrik Keinonen, Travis Schnider, and Tao Su
Hey, I think one bit is not true. You said that the output of the log transducer can be arbitrary big but I think it can be polynomial at most (because there is only polynomial number of configurations right? Number of configs = |Q| * n * log n * d^O(log n) which is some polynomial value.
I agree, and this is important because the B machine doesn't use log(n) space but rather log(m) space where m is the length of the output from the reduction, so we need to use the fact that m can only be as big as a polynomial of n which means log(m) = log(n)
Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are in the video description. Names are listed in alphabetical order by surname.
Platinum: Micah Wood
Silver: Simone Glinz, Josh Hibschman, Timmy Gy, Patrik Keinonen, Travis Schnider, and Tao Su
Hey, I think one bit is not true. You said that the output of the log transducer can be arbitrary big but I think it can be polynomial at most (because there is only polynomial number of configurations right? Number of configs = |Q| * n * log n * d^O(log n) which is some polynomial value.
I agree, and this is important because the B machine doesn't use log(n) space but rather log(m) space where m is the length of the output from the reduction, so we need to use the fact that m can only be as big as a polynomial of n which means log(m) = log(n)
I have no log experience
Hey 👋