= 27d567bc2d48d9f40e9ccc20ea370b15)
wedrifid 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)
Bear in mind that if we zoom in to sufficiently fine granularity, we can get literally infinite speedup -- some of my most productive programming days have been when I've found a way to make a section of code unnecessary, and delete it entirely.
To show this part of my argument is not infinitely flexible, I will say one algorithmic breakthrough that would invalidate it, would be a constructive proof of P=NP (or a way to make quantum computers solve NP-complete problems in polynomial time - I'm told the latter has been proven impossible, but I don't know how certain it is that there aren't any ways around that).
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).