Skip to content
Home » Tractable and Intractable Problems

Tractable and Intractable Problems

1. Introduction

In Computational Complexity, problems are not only studied based on whether they can be solved, but also how efficiently they can be solved.

Some problems can be solved efficiently even when the input size becomes large. These are called Tractable Problems.

Some problems can be solved in principle, but require a very large amount of time or computational resources as the input size increases. These are called Intractable Problems.

Important: Intractable does not mean impossible. An intractable problem may still be solvable, but it may be impractical for large inputs.


2. Tractable Problems

Definition

A problem is called tractable if it can be solved efficiently, generally using an algorithm whose running time is polynomial in the size of the input.

Examples of polynomial time:\[ O(n),\quad O(n^2),\quad O(n^3),\quad O(n^5) \]

where \(n\) is the input size.

Example

Suppose an algorithm searches through \(n\) elements one by one.

Its time complexity is:\[ O(n) \]

Even if \(n\) becomes large, the running time increases in a relatively manageable way.

Common examples

  • Searching in a sorted array using Binary Search – \(O(\log n)\)
  • Finding the shortest path using suitable algorithms – polynomial time
  • Sorting using Merge Sort – \(O(n\log n)\)
  • Minimum Spanning Tree – polynomial time
  • Many graph and optimization problems

3. Intractable Problems

Definition

A problem is called intractable when it is computationally very expensive to solve, especially when the input size becomes large.

Typically, in complexity theory, problems requiring exponential or factorial time are considered practically intractable.

Examples:\[ O(2^n) \]\[ O(3^n) \]\[ O(n!) \]

Example

Suppose an algorithm takes:\[ O(2^n) \]

For \(n=10\):\[ 2^{10}=1024 \]

For \(n=50\):\[ 2^{50}\approx 1.12\times10^{15} \]

So, a small increase in input size can make the computation extremely expensive.


4. Tractable vs Intractable

FeatureTractableIntractable
MeaningEfficiently solvableComputationally expensive
Typical complexityPolynomialUsually exponential/factorial
Examples\(O(n), O(n^2), O(n\log n)\)\(O(2^n), O(n!)\)
Large inputUsually manageableOften impractical
Algorithm exists?YesUsually yes
Related classMainly POften NP-hard/NP-complete problems
Practical useUsually feasibleMay become impractical

5. Polynomial vs Exponential Growth

Consider the following:

\(n\)\(n^2\)\(2^n\)
101001,024
204001,048,576
309001,073,741,824
401,6001,099,511,627,776

This shows why polynomial-time algorithms are generally preferred.

Simple idea:

Polynomial growth → manageable

Exponential growth → rapidly becomes expensive


6. Relationship with P and NP

The concept of tractability is closely related to the complexity class P.

P

P (Polynomial Time) is the class of decision problems that can be solved by a deterministic algorithm in polynomial time.

Therefore:\[ \boxed{P \approx \text{Tractable Problems}} \]

This is a useful practical interpretation, although “tractable” is a broader informal term.

NP

NP contains decision problems whose solutions can be verified in polynomial time.

Some NP problems may have polynomial-time algorithms, but for many important NP-complete problems, no polynomial-time algorithm is currently known.

For example:

  • SAT
  • 3-SAT
  • Traveling Salesman Problem (decision version)
  • Hamiltonian Cycle
  • Clique

These are NP-complete problems.

If any NP-complete problem is solved in polynomial time, then:\[ P=NP \]


7. Important: Intractable ≠ Unsolvable

This is a very important examination point.

Intractable Problem

An algorithm exists, but the computation may require enormous resources.

Unsolvable Problem

No algorithm exists that can solve all instances correctly and halt.

IntractableUnsolvable
Algorithm existsNo general algorithm exists
Can theoretically be solvedCannot be solved by any algorithm
May take enormous timeNo guaranteed solution method
Example: many NP-hard optimization problemsHalting Problem
Complexity issueComputability issue

Remember:

Intractable = Too difficult/expensive to compute efficiently.

Unsolvable = No general algorithm exists.


8. Example: Traveling Salesman Problem

The Traveling Salesman Problem (TSP) asks:

Given a set of cities and distances between them, find the shortest possible route that visits every city exactly once and returns to the starting city.

For \(n\) cities, a brute-force method may need to examine approximately:\[ (n-1)! \]

possible routes.

For example:\[ 5! = 120 \]

but\[ 20! \approx 2.43\times10^{18} \]

Thus, brute-force TSP becomes extremely expensive as the number of cities increases.

The optimization version of TSP is NP-hard, while the corresponding decision version is NP-complete.


9. Why Do We Study Tractable and Intractable Problems?

They help us:

  1. Select efficient algorithms.
  2. Estimate computational resources.
  3. Handle large input sizes.
  4. Decide whether an exact solution is practical.
  5. Look for approximation or heuristic algorithms for difficult problems.
  6. Understand the limits of computation.
  7. Classify problems into complexity classes.

10. Relationship with Previous Topics

You can remember the complete picture like this:

COMPUTATIONAL PROBLEMS
          |
          v
   Can it be solved?
      /          \
    YES           NO
     |             |
     v             v
  Solvable      Unsolvable
     |
     v
How efficiently?
     |
     +----------------+
     |                |
     v                v
 Tractable       Intractable
     |                |
 Polynomial       Very expensive
 time             computation
     |                |
     v                v
     P          NP-Hard / NP-Complete*

\(*\text{Many important NP-hard/NP-complete problems are considered intractable, although the exact P vs NP question remains open.}\)


11. Key Points for Examination

  • Tractable problems can generally be solved efficiently.
  • Polynomial-time algorithms are considered tractable.
  • Intractable problems require very high computational resources as input size increases.
  • Exponential and factorial algorithms are typical examples of computationally intractable approaches.
  • P is generally associated with tractable decision problems.
  • Many NP-complete problems are believed to be intractable.
  • Intractable does not mean unsolvable.
  • The Halting Problem is unsolvable, not merely intractable.
  • Whether \(P=NP\) is still an open problem.

5–10 Marks Exam Answer

Tractable and Intractable Problems

A tractable problem is a computational problem that can be solved efficiently, generally using a polynomial-time algorithm. Its running time can be represented by complexities such as \(O(n)\), \(O(n^2)\), or \(O(n^3)\). Such problems remain practically manageable even for relatively large inputs. Problems in the class P are generally considered tractable.

An intractable problem is a problem for which the known algorithms require very large computational resources, particularly exponential or factorial time such as \(O(2^n)\) or \(O(n!)\). Such problems may be solvable in theory but become impractical for large inputs.

Examples of difficult problems include Travelling Salesman Problem, SAT, 3-SAT, Clique and Hamiltonian Cycle. Many of these are NP-complete or NP-hard.

It is important to distinguish intractable from unsolvable. An intractable problem has a solution algorithm but may require excessive resources, whereas an unsolvable problem has no general algorithm that can solve every instance and halt.

Thus:\[ \boxed{\text{Tractable} \rightarrow \text{Efficiently Solvable}} \]\[ \boxed{\text{Intractable} \rightarrow \text{Solvable but Computationally Expensive}} \]\[ \boxed{\text{Unsolvable} \rightarrow \text{No General Algorithm}} \]

Fast Memory Trick

T-I-U = Time

  • T = Tractable → Time is manageable
  • I = Intractable → Immense time
  • U = Unsolvable → Universal algorithm does not exist

And remember:

P → Practical, NP-complete → Probably difficult, Undecidable → Impossible algorithmically.