Complexity Theory

Complexity Classes §

---

P

P refers to Polynomial, the complexity class of problems that are deemed to be tractable i.e. solved in worst-case polynomial time of $O(n^c)$ or less. A P-class problem can be verified in polynomial time as well.

A P-Class problem will have the following Big-O time complexities:

• $O(n)$ - Linear
• $O(log(n))$ - Log
• $O(n\ast log(n))$ - Loglinear
• $O(n^c)$ - Polynomial

Examples §

• Determining whether a number is prime
• All searches and sorts
• Matrix Multiplication

Link to source

---

NP

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 §

#todo List NP Problems that are neither NP-Complete nor NP-Hard

Link to source

---

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

Link to source

---

NP-Hard

NP-Hard is a set of problems that cannot be solved in polynomial time and may or may not be verifiable in polynomial time. If an NP-Hard problem is solved, it can be used to solve every other NP problem.

Examples §

• The Optimal TSP problem
• Obtaining the chromatic number of a graph i.e Optimisation Graph Colouring
• The Halting Problem (NP-Hard ONLY)

Link to source

Resources §