You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

JoshuaZ comments on Open Thread, October 13 - 19, 2013 - Less Wrong Discussion

4 Post author: Coscott 14 October 2013 01:57AM

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

Comments (247)

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

Comment author: JoshuaZ 23 October 2013 03:19:02PM 0 points [-]

Conditional on P=NP, what odds do you put that P is not P^#P or PSPACE? (though maybe the first is a robust hypothesis that doesn't cover BQP)

I'm not sure. If P=NP this means I'm drastically wrong about a lot of my estimates. Estimating how one would update conditioning on a low probability event is difficult because it means there will be something really surprising happening, so I'd have to look at how we proved that P=NP to see what the surprise ended up being. But, if that does turn out to be the case, I'm fairly confident I'd then assign a pretty high probability to P=PSPACE. On the other hand we know that of the inequalities between P, NP, PSPACE and EXP, at least one of them needs to be strict. So why should I then expect it to be strict on that end? Maybe I should then believe that PSPACE=EXP? PSPACE feels closer to P than to EXP but that's just a rough feeling, and we're operating under the hypothetical that we find out that a major intuition in this area is wrong.