Timeline for Prove that $TQBF \notin SPACE(n^{\frac{1}{3}})$
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 5, 2021 at 13:29 | comment | added | mike | @YuvalFilmus thanks for the answer but I think this part of your answer "Since TQBF is PSPACE-complete, there is some logspace reduction from L to TQBF" is a bit misleading and it needs a change. please look at the cs.stackexchange.com/questions/90527/… . | |
| Dec 4, 2020 at 23:33 | comment | added | Macrophage | Ah, sorry...I see it now, it's bounded by Savitch's theorem. | |
| Dec 4, 2020 at 23:29 | comment | added | Macrophage | More specifically, I'm wondering how we can put an upper bound on the size of the output of the logspace reduction to TQBF. | |
| Dec 4, 2020 at 23:27 | comment | added | Macrophage | Thanks, I just tried to derive that TQBF is indeed complete using logspace reduction. But I still have some question about what "blowing up" instances mean in your answer. I'm trying to prove by contradiction and somehow use the padding argument. | |
| Dec 4, 2020 at 22:21 | comment | added | Yuval Filmus | Different notions of reductions are used in different places. | |
| Dec 16, 2013 at 20:45 | vote | accept | InsigMath | ||
| Dec 16, 2013 at 20:44 | comment | added | InsigMath | Hey @YuvalFilmus if you are interested in the solution to this problem, here is another version of this problem with exponent $n^{\frac{1}{4}}$ as solved by Professor Cook - cs.toronto.edu/~sacook/csc463h/problems/solutions4.pdf it's question 4 | |
| Dec 11, 2013 at 8:44 | history | answered | Yuval Filmus | CC BY-SA 3.0 |