Kevin Wampler wrote:

> Integer factorization, for instance, has no known polynomial time 
> algorithm but there are known sub-exponential algorithms.

Really? I was under the impression that just recently - ah, wait. No, 
they found a polynomial-time primality test, but factorisation. Oh well.

> One other point which I have messed up before and had Warp correct me 
> on.  The NP and NP-complete complexity classes are for *decision 
> problems* only.

Yeah, I thought that was the case...

Post a reply to this message