A tractable problem is one that has any algorithm that runs in polynomial time or lesser. Any problem that takes longer is defined to be intractable.

Tractable

Cobham’s thesis states that in order for a problem to be tractable, it should have an algorithm of polynomial order.

Problems solved by algorithms that are for some constant are polynomial-time P-class problems. These are considered tractable, feasible, reasonable problems.

Intractable

An intractable problem is one that is solved by an algorithm in unreasonable time

Problems that have the quickest algorithms that run in exponential time are intractable, unfeasible, unreasonable problems. Depending on whether their solution can be checked in polynomial time, they are NP, NP-Complete or NP-Hard problems.

combinatorial explosion in the size of a decision trees as a function of the input size (n) makes a problem intractable (i.e. unsolvable in reasonable time).