Tractable Problems

A problem is tractable if it can be solved in polynomial time — i.e. there exists an algorithm with time complexity O(nᵏ) for some constant k. Tractable problems are considered practically solvable for large inputs.

• O(1), O(log n), O(n), O(n log n), O(n²), O(n³) — all polynomial → tractable
• Examples: sorting (merge sort O(n log n)), searching (binary search O(log n)), matrix multiplication

Intractable Problems

A problem is intractable if no polynomial-time algorithm is known — the best known algorithms are super-polynomial (e.g. exponential or factorial). Intractable problems are considered practically unsolvable for large inputs.

• O(2ⁿ), O(n!) — exponential and factorial → intractable
• Even fast computers cannot solve large intractable instances in any reasonable time

Examples of intractable problems

Approaches for intractable problems

• Heuristics — find a "good enough" approximate solution quickly (not guaranteed optimal)
• Limit input size — solve only small instances exactly
• Approximation algorithms — guaranteed bounds on how far from optimal

The P vs NP Problem

P — the class of problems solvable in polynomial time by a deterministic computer.

NP — the class of problems where a solution can be verified in polynomial time. (NP stands for Non-deterministic Polynomial time.)

• TSP: given a proposed tour, verifying it visits all cities with total distance ≤ k is O(n) — so TSP is in NP
• The famous open question: P = NP? — is every problem whose solution can be verified quickly also solvable quickly?
• Most computer scientists believe P ≠ NP, but it remains unproven

The Halting Problem

The Halting Problem asks: Given any program P and any input I, will P eventually halt (terminate) or loop forever?

Alan Turing proved in 1936 that no general algorithm can solve the Halting Problem — it is undecidable.

Turing's proof by contradiction

// Suppose a program H(P, I) exists that returns:
//   true  → P(I) halts
//   false → P(I) loops forever

// Construct a program D(P) that:
//   if H(P, P) = true  → D loops forever
//   if H(P, P) = false → D halts

// Now run D(D):
//   If H(D, D) = true  → D(D) should halt, but D loops → contradiction!
//   If H(D, D) = false → D(D) should loop, but D halts  → contradiction!

// Therefore H cannot exist.

Why the Halting Problem matters

• It proves there are problems that are computationally unsolvable — no algorithm can ever solve them
• It establishes limits on what computers can do
• Many practical problems (e.g. "does this program have a bug?", "does this program ever output X?") are undecidable for the same reason