Do you remember what an NP-complete problem is? How does it differ from NP?

NP (nondeterministic polynomial time) — is a class of problems for which a solution can be verified in polynomial time. That is, if you have a candidate answer, you can quickly check whether it is correct or not.

NP-complete problems are a subset of NP that are simultaneously the "hardest" in this class. If someone found a polynomial algorithm for solving any NP-complete problem, then all problems in NP could be solved in polynomial time.

Main differences:

• NP — problems for which solutions can be quickly verified.
• NP-complete — problems in NP to which any other NP problem can be reduced (meaning they are "the most difficult" in NP).

Example: the maximum clique problem in a graph — NP-complete, and the problem of checking whether a subset of elements sums to a given number — in NP.