On Wed, Oct 08, 2014 at 11:48:20AM -0400, Riad S. Wahby wrote: > Georgi Guninski <[email protected]> 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! >
ok, this is the popular scientific opinion, i am noob at complexity theory. just to point out that if a deity offers me crypto stuff that is breakable in polynomial time, but provably not less than say O(n^1000), i wouldn't care about P vs NP and will choose $n$ large enough, might be wrong. > Quantum computation is not magic; the limits of quantum mechanics > already imply relatively strong lower bounds for quantum hash > collision search. > > -=rsw
