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.

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.