News for hackers. Stuff that matters.
Re:Moore’s Law won’t kill passwords by eru on Friday January 18, 2013 @03:16AM (#5077698)
To go off a tangent: Quantum computers are not real, yet, but we already have a handle on the complexity class of problems they will be able to solve in polynomial time.

(We do not know everything about that class, yet. But we strongly suspect that it is neither a superset nor a subset of NP.)

Re:Moore’s Law won’t kill passwords by dchest on Friday January 18, 2013 @03:55AM (#5077786)
Brute force on quantum computer will require around 2^(n/2) invocations of algorithm, compared to 2^n on classical computer. Not a huge problem.

http://en.wikipedia.org/wiki/Key_size#Effect_of_quantum_comp...

Re:Moore’s Law won’t kill passwords by tiziano88 on Friday January 18, 2013 @05:03AM (#5077965)
I was under the impression that QNP (the class of problems solvable by a quantum non-deterministic Turing machine in P-time) is a (non strict) subset of NP. Things might have changed since I last checked though.
Re:Moore’s Law won’t kill passwords by eru on Friday January 18, 2013 @08:05AM (#5078417)
Did you mean superset instead of subset?

Anyway for my statement I was only interested deterministic polynomial time (perhaps with access to randomness) with or without quantum capabilities.

"Why Philosophers Should Care About Computational Complexity" (http://arxiv.org/abs/1108.1791v3) is a good read about this---amongst other things.

Re:Moore’s Law won’t kill passwords by tiziano88 on Friday January 18, 2013 @08:17AM (#5078459)
I did mean subset, apparently a quantum computer could not solve every NP-complete problem in polynomial time. factorisation seems to be one of the candidates to benefit from quantum computation (thanks to Shor's algorithm), but SAT (for instance) would not, at least based on current state-of-art
Re:Moore’s Law won’t kill passwords by eru on Friday January 18, 2013 @10:14AM (#5078987)
Yes, I know.

So I guess if you meant subset, then you didn't mean to write "quantum ___non-deterministic___ Turing machine in P-time"?