Algorithm Complexity
P = solutions in polynomial deterministic time.
NP = (non-deterministic polynomial time) solutions checkable in deterministic polynomial time.
- e.g. RSA code breaking by factoring
NP-complete = most complex subset of NP
- e.g. traveling all vertices with mileage < x
NP-hard = optimization versions of above
- e.g. Minimum mileage for traveling all vertices
Undecidable = no way even with unlimited time & space
- e.g. program halting problem