Complexity Classes: P, NP, NP-Hard, and NP-Complete

Decision Problems

Complexity classes are defined for decision problems — problems with a yes/no answer (e.g., “Is there a Hamiltonian path in this graph?”).

Optimisation problems can often be reframed as decision problems: “Is there a tour of length ≤ $k$?” instead of “Find the shortest tour.”

Class P (Polynomial Time)

P = the set of decision problems solvable in polynomial time by a deterministic algorithm.

$$P = {L : L \text{ is decidable in } O(n^k) \text{ for some constant } k}$$

Properties:
- “Efficient” — practically feasible for large inputs
- Includes most of the algorithms studied in VCE Algorithmics

Examples:
- Sorting: $O(n \log n)$
- Shortest path (Dijkstra’s): $O((V+E)\log V)$
- MST (Prim’s): $O((V+E)\log V)$
- BFS, DFS: $O(V+E)$

KEY TAKEAWAY: P contains problems we can solve efficiently. Most real-world algorithms you study belong to P.

Class NP (Non-deterministic Polynomial Time)

NP = the set of decision problems where a proposed solution can be verified in polynomial time.

Key insight: Verifying a solution is easy, even if finding it is hard.

Examples:
- Travelling Salesman (decision): Given a tour, checking if its length ≤ $k$ is $O(n)$ — easy to verify
- Graph Colouring: Given a colouring, checking validity is $O(n + E)$ — easy to verify
- 0-1 Knapsack: Given a selection, checking total weight ≤ $W$ and value ≥ $v$ is $O(n)$ — easy to verify

Relationship: $P \subseteq NP$ (if you can solve it, you can certainly verify a solution). The famous unsolved question: Is P = NP? Most researchers believe $P \neq NP$.

NP-Complete

NP-Complete = problems that are:
1. In NP (solutions can be verified in polynomial time)
2. NP-Hard (every problem in NP can be reduced to them in polynomial time)

NP-Complete problems are the hardest problems in NP. If any NP-Complete problem were solvable in polynomial time, then P = NP.

Examples:
- Travelling Salesman Problem (decision version)
- Graph 3-Colouring
- 0-1 Knapsack
- Boolean Satisfiability (SAT — the first proven NP-Complete problem)
- Hamiltonian Path/Cycle

NP-Hard

NP-Hard = problems at least as hard as the hardest problems in NP. NP-Hard problems:
- May or may not be in NP themselves
- Include NP-Complete problems
- Also include problems harder than NP (e.g., optimisation versions of NP-Complete problems)

Examples:
- Travelling Salesman Problem (optimisation: find shortest tour) — NP-Hard but not in NP (output is a number, not a yes/no)
- Halting Problem — undecidable, and thus “harder than NP-Hard”

Summary Diagram

       ┌─────────────────────────────────┐
       │            NP-Hard              │
       │  ┌──────────────────────────┐   │
       │  │        NP                │   │
       │  │  ┌─────────────────┐     │   │
       │  │  │       P         │     │   │
       │  │  └─────────────────┘     │   │
       │  │   NP-Complete ← in NP    │   │
       │  │     AND NP-Hard          │   │
       │  └──────────────────────────┘   │
       └─────────────────────────────────┘
         (assuming P ≠ NP)

Practical Implications

• If a problem is NP-Hard, no known polynomial-time algorithm exists.
• For NP-Hard problems, use: heuristics, approximation algorithms, or exact algorithms for small inputs.
• Knowing a problem is NP-Hard tells you to stop looking for an efficient exact algorithm and instead use a different strategy.

EXAM TIP: Be clear on the distinction: P = solvable efficiently; NP = verifiable efficiently; NP-Complete = hardest in NP; NP-Hard = at least as hard as NP-Complete. Know concrete examples of each.