15 Oct
2014
15 Oct
'14
1:11 p.m.
On Wed, Oct 08, 2014 at 11:48:20AM -0400, Riad S. Wahby wrote:
Georgi Guninski <guninski@guninski.com> wrote:
second, it is not known even if P ≠ NP, can a sufficiently powerful quantum computer solve SAT efficiently? -- if the answer is ``yes'' djb & co fail.
And yet a quantum computer efficiently solving SAT would be substantially more surprising than P=NP!
Quantum computation is not magic; the limits of quantum mechanics already imply relatively strong lower bounds for quantum hash collision search.
-=rsw
Are the limits of quantum mechanics known at all? As I wrote it might turn out that classic computer might break SAT efficiently, though this doesn't appear on man pages of broken warez ;)