NP-Class

NP refers to Non-Deterministic Polynomial, the class of problems that are intractable to solve but can be verified reasonably. These set of problems have a worst-case time that is great than polynomial time i.e. $>O(n^c)$

An NP-Class problem will have the following Big-O time complexities:

• $O(n!)$
• $O(c^n)$
• $O(n^n)$

Examples §

---

• 0-1 Knapsack Problem
• Boolean Satisfiability Problem
• N-Queens Problem
• Travelling Salesman Problem (TSP)

---

• Integer Factorisation