Sniffnoy comments on Open Thread: May 2010, Part 2 - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (348)
Quick note, P != PSPACE is not in fact proven.
Unrelated addendum: It occurs to me that Harry was able to get the "Do not mess with time" message because his outputs and inputs were insufficiently digital. He considered the possibility of getting nothing, but didn't think to lump in with it the possibility of getting anything outside of the range specified. Why did he get specifically that message, preventing him from noticing the problem is easily fixable? Because this is CS world, of course, so we assume that nature chooses adversarially...
Right sorry, we know that P != EXP from the hierarchy results. (Gah. Should have realize that made no sense to think that P != PSPACE could come from from hierarchy results, given that one is a time defined set and one is a space defined set in order to get that one would probably need an intermediate computational class or a deep equivalence).
Edit: I should also probably specify that Sniffnoy was the person who made me aware of the the Aaronson work cited above.