State Hash
Georgi Guninski
guninski at guninski.com
Wed Oct 8 08:59:29 PDT 2014
On Wed, Oct 08, 2014 at 11:48:20AM -0400, Riad S. Wahby wrote:
> Georgi Guninski <guninski at 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!
>
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
More information about the Testlist
mailing list