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.

Douglas_Knight 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: Douglas_Knight 23 October 2013 06:37:57AM 1 point [-]

Sure, but that's just saying that P=NP is not a robust hypothesis. 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)

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.