Warp wrote:
>   Basically the NP complexity class is composed of those problems for
> which the solution cannot, as far as we currently know, be solved in
> polynomial time using a deterministic computer (which means that solving
> the problem requires at least exponential time), but if a solution is
> given, the solution can be verified in polynomial time.

It's a minor quibble, but I don't think this bit of reasoning holds. 
Integer factorization, for instance, has no known polynomial time 
algorithm but there are known sub-exponential algorithms.  Also (as I'm 
sure you know, but Andrew may not) polynomial time algorithms are 
considered part of the NP class, just as far as we know they're disjoint 
from the NP-complete class.

> 
>   (Note that a solution to an NP-complete problem might not be usable as
> a solution to the so-called NP-hard problems, so it makes a difference
> whether a problem is NP or NP-hard.)
> 

I found this picture handy in describing this relationship:

http://upload.wikimedia.org/wikipedia/commons/a/a0/P_np_np-complete_np-hard.svg


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.  That is algorithms which only return a boolean as their 
result.  If you want to refer to complexity classes for algorithms which 
  return more complicated results, the correct terms are FP (instead of 
P) and FNP (instead of NP).

Post a reply to this message