Sniffnoy comments on Open Thread: May 2010, Part 2 - Less Wrong

3 Post author: Kevin 20 May 2010 07:30PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (348)

You are viewing a single comment's thread. Show more comments above.

Comment author: Sniffnoy 25 May 2010 07:35:57PM *  3 points [-]

There's been serious examination of this sort of time loop before. See Scott Aaronson's remarks which show that it in fact allows you to solve quickly not just NP problems but also everything in PSPACE (which is noteworthy because we know that P != PSAPCE).

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...

Comment author: JoshuaZ 25 May 2010 07:52:22PM *  2 points [-]

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.