Also known as: Np completeness
NP-completeness is a concept in computational complexity theory for problems that are both in NP and at least as hard as every other problem in NP. Such problems have solutions that can be verified efficiently, but no known general method solves all instances efficiently.
In computational complexity theory, a problem is NP-complete when it can be solved by a restricted class of brute force search algorithms and it can be used to simulate any other problem with a similar algorithm. More precisely, each input to the problem should be associated with a set of solutions of polynomial length, whose validity can be tested quickly (in polynomial time), such that the output for any input is "yes" if the solution set is non-empty and "no" if it is empty.