NP-completeness
NP-completeness is a label for a family of problems that share a strange double nature: a proposed answer can be checked quickly, but finding that answer seems to require searching an enormous space with no known shortcut. 'NP' is the class of problems whose 'yes' answers come with a certificate you can verify in polynomial time. A Sudoku puzzle is the friendly picture: confirming that a filled-in grid is valid takes seconds, yet solving a blank one can be agonizing. The NP-complete problems are the hardest problems in NP.
What makes them special is captured by reduction. A problem is NP-complete if it is in NP and every other problem in NP can be transformed into it efficiently — so if you ever found a genuinely fast (polynomial-time) algorithm for one NP-complete problem, you could translate any NP problem into it and solve all of them fast. This is why they are called the 'hardest in NP': they are all tied together by these translations. Famous members include Boolean satisfiability (SAT), the decision version of the traveling-salesman problem (is there a tour shorter than k?), graph coloring, and the knapsack problem.
The practical meaning is sobering but useful. If you prove your problem is NP-complete, you are not being told it is impossible — you are being told that nobody on Earth currently knows a method that scales well, so chasing a fast exact algorithm is probably a waste of effort. Instead you reach for other tools: approximation algorithms that get close, heuristics that work well in practice, exact solvers for small inputs, or exploiting special structure in your particular data. The label redirects your effort rather than ending it.
// SAT, e.g. (a OR !b) AND (b OR c)
// Verifying a proposed assignment is fast:
bool satisfies(const Formula& f, const Assignment& a) {
for (const Clause& c : f.clauses)
if (!c.isTrueUnder(a)) return false; // O(total literals)
return true;
}
// But finding a satisfying assignment among 2^n possibilities
// has no known polynomial-time algorithm.Verifying a candidate is O(formula size); searching all assignments is exponential.
NP-complete does not mean 'proven impossible' — it means no fast algorithm is known, and finding one for any single such problem would crack them all.