8 Oct
2014
8 Oct
'14
3:48 p.m.
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