# P, NP, NP-complete

- A problem is in class
`P`

if its solution may be *found* in polynomial time.
- A problem is in class
`NP`

if its solution may be *verified* in polynomial time.
- A problem in
`P`

is in `NP`

by definition, but the converse may not be the case.
`NP`

-complete is a family of `NP`

problems for which you know that if one of them has a polynomial solution then everyone of them has.
- Examples of
`NP`

-complete problems: traveling salesman, knapsack, graph coloring.
- Once you've reduced a problem to
`NP`

-complete, you know to give up on an efficient fast algorithm and to start looking at approximations.
- For
`NP`

-complete problems, no polynomial-time algorithms are known for solving them (although they can be verified in polynomial time).
- The most notable characteristic of
`NP`

-complete problems is that no fast solution to them is known.
`NP`

-hard: non-deterministic polynomial time.