16 Algorithmic Paradigm to cope with NP-hardness

Assuming $\mathbf{P}\ne \mathbf{NP}$, a problem $X$ being $\mathbf{NP}$-hard implied that we cannot have an algorithm ALG for which it satisfies both of the following properties:

• ALG is always correct (1)
• ALG runs in polynomial time (2)

This has led to development of new algorithmic paradigms such as:

1. (Exact) Exponential Algorithms (satisfy (1) violate (2))
2. (Polytime) Approximation Algorithms (satisfy (2) violate (1) approximately)
3. (Polytime) Randomisation Algorithms (satisfy (1) violate (1) approximately)
4. Parameterised Algorithms