NP-Complete

NP-Complete problems are an intersection of NP and NP-Hard problems. Therefore they must be verifiable in polynomial time (to be in NP) and is at least as hard as the hardest problem in NP (NP-Hard definition). All NP-Complete problems are related, and they can all become the same problem

Examples §

• TSP Decision Problem
• Knapsack Problem: $O(2^n)$
• Tower Of Hanoi: $O(2^n-1)$
• Determining whether a graph has Hamiltonian cycles or paths (subset of TSP): $O(n!)$
• N-Queens Problem