1. Non deterministic Polynomial. Of a computational problem whose solution is easy to verify (doable in polynomial
time of the size of the input).
2. Abusively used to describe a problem that is not P, that is which has no solution in polynomial
time. A "complex
number" rarely refers to a number such has 2, even though 2 technically is a complex number ; likewise stating a problem is NP often implicitely conveys that it is just that, even though P is included in NP. NP-C and NP-
hard are more specific terms though they don'
t describe intermediate problems and what they describe depends on the result of P=NP?