= 27d567bc2d48d9f40e9ccc20ea370b15)
paulfchristiano comments on The Curve of Capability - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (264)
There are no known strong results concerning the relationship between BQP (roughly the analogue of P for quantum computers) and NP. There is strong consensus that BQP does not contain NP, but it is not as strong as the overwhelming consensus that P != NP.
Presumably because P = NP would imply that NP is contained in BQP, so you can't believe the first of your statements without believing the second.
It's not even known if NP contains BQP?
No. The best we can do is that both contain BPP and are contained in PP, as far as I recall.
And there exist oracles relative to which BQP is not contained in MA (which contains NP).