3.3.2 Tractable vs. Intractable Problems
Algorithms and Problem Solving
Once a problem is determined to be solvable, the next consideration is its computational complexity—how efficiently it can be solved. Problems are categorized as tractable or intractable based on the resources required (time and space) to solve them.
Tractable Problems: A problem is considered tractable if it can be solved in polynomial time, denoted as P. Polynomial time means that the time taken to solve the problem increases at a manageable rate (as a polynomial function) relative to the size of the input. Tractable problems are considered "efficiently solvable."
Example: Sorting a list of numbers using algorithms like Merge Sort or Quick Sort is a tractable problem because these algorithms have a polynomial time complexity of O(n log n), where n is the number of elements in the list.
Intractable Problems: Intractable problems are those that require super-polynomial time to solve, often growing exponentially with the size of the input. These problems are impractical to solve for large inputs because the time required becomes unmanageable.
Example: The Travelling Salesman Problem (TSP), where the goal is to find the shortest possible route that visits a set of cities and returns to the origin, is an example of an intractable problem. The problem is NP-hard, meaning that as the number of cities increases, the number of possible routes grows factorially, making it infeasible to solve exactly for large instances. Factorially means, multiplying all whole numbers from n down to 1.
- For 2 cities: 2! = 2 x 1=2 possible routes.