Timeline for Prove that $TQBF \notin SPACE(n^{\frac{1}{3}})$
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 10, 2016 at 15:34 | comment | added | Kaveh | @Yuval, this is an exercise in Sipser about padding IIRC. | |
| Jan 8, 2014 at 5:30 | history | tweeted | twitter.com/#!/StackCompSci/status/420789506229665792 | ||
| Dec 16, 2013 at 20:45 | vote | accept | InsigMath | ||
| Dec 11, 2013 at 8:45 | comment | added | Yuval Filmus | This is actually not quite as easy as I had assumed. | |
| Dec 11, 2013 at 8:44 | answer | added | Yuval Filmus | timeline score: 4 | |
| Nov 28, 2013 at 8:17 | review | Close votes | |||
| Jan 6, 2014 at 12:41 | |||||
| Nov 28, 2013 at 5:29 | comment | added | InsigMath | Thanks we were told that it is logspace reducible. I understand that you cannot give anymore hints without basically spelling out the solution. I will think more deeply about this question. Have a good evening @YuvalFilmus | |
| Nov 28, 2013 at 2:13 | comment | added | Yuval Filmus | By the way, TQBF being PSPACE-complete means that TQBF is in PSPACE, and any problem in PSPACE is polytime-reducible to it. (Perhaps even logspace-reducible.) | |
| Nov 28, 2013 at 2:12 | comment | added | Yuval Filmus | I cannot give you any more hints than the facts you've already mentioned. | |
| Nov 27, 2013 at 22:03 | history | asked | InsigMath | CC BY-SA 3.0 |