Classification of Algorithms: Tractable, Intractable, and Computable

Algorithms are not just about finding a correct solution — they must find it in a practical amount of time. This lesson explores how algorithms are classified by their complexity and what this means for real-world problem solving.

The Classification Framework

Class	Definition	Examples
Computable	A problem that can be solved by an algorithm (a Turing machine that halts on all inputs)	Sorting, searching, shortest path
Non-computable	A problem that cannot be solved by any algorithm	The Halting Problem
Tractable	A computable problem with a polynomial-time solution — O(nᵏ) for some constant k	Sorting (O(n log n)), shortest path (O(V²))
Intractable	A computable problem with no known polynomial-time solution — best known algorithms are exponential or worse	Travelling Salesman (O(n!)), Boolean satisfiability

Polynomial vs Exponential Growth

Complexity	Type	n = 10	n = 20	n = 50	Tractable?
O(n)	Polynomial	10	20	50	Yes
O(n²)	Polynomial	100	400	2,500	Yes
O(n³)	Polynomial	1,000	8,000	125,000	Yes
O(2ⁿ)	Exponential	1,024	1,048,576	~10¹⁵	No
O(n!)	Factorial	3,628,800	~2.4 × 10¹⁸	~3 × 10⁶⁴	No

The boundary between tractable and intractable is the line between polynomial and exponential/factorial growth.

Complexity Classes: P and NP

Class P

P is the set of all decision problems (yes/no problems) that can be solved in polynomial time.

Examples: Is this list sorted? Is this number prime? Can you find the shortest path?

Class NP

NP (Non-deterministic Polynomial) is the set of all decision problems where a proposed solution can be verified in polynomial time.

Example: The Travelling Salesman Problem. Given a proposed route, we can easily check whether its total distance is below a threshold in O(n) time. But finding the optimal route may require exponential time.

Key relationship:

Every problem in P is also in NP (if you can solve it quickly, you can certainly verify a solution quickly).
P ⊆ NP.
The big open question: Does P = NP? Nobody knows. This is the most famous unsolved problem in Computer Science.

NP-Complete and NP-Hard Problems

NP-Complete

A problem is NP-complete if:

It is in NP (solutions can be verified in polynomial time).
Every other problem in NP can be reduced to it in polynomial time.

NP-complete problems are the "hardest" problems in NP. If a polynomial-time algorithm is found for any NP-complete problem, then all NP problems can be solved in polynomial time (P = NP).

Famous NP-complete problems:

Boolean Satisfiability (SAT) — the first problem proved NP-complete
Travelling Salesman (decision version)
Graph Colouring
Knapsack Problem
Subset Sum

Classification of Algorithms