NP-Completeness

For a problem X to be NP-complete, it needs to satisfy two properties:

• X is in NP (short accepting certificate).
• X is NP-hard (an NP-hard problem can be reduced to it).

The NP-complete problems are the hardest problems in NP. If even one of them can be solved in polynomial time, then they all can.

Books of such problems exist...