An Aside: Complexity Classes (cont)
The P and NP classes suggest "level of difficulty":
- P ... "easy" ... has known polynomial-time algorithm
- NP ... "hard" ... no P algorithm known
Another characterisation of "difficulty":
- easy ... have a polynomial-time algorithm (useful in practice)
- tractable ... have an algorithm, feasible only for small N
- intractable ... no tractable algorithm is known (NP-hard)
- non-computable ... no algorithm can exist
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}