A tractable computational problem is one that has any algorithm that has a Big-O of polynomial time or lesser. Such an algorithm is known to be efficient. 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-Class, NP-Complete or NP-Hard problems.
While some these problems are intractable, there are various workarounds:
- Restrictions on the input set: For example, while the TM Acceptance Problem is undecidable (and therefore intractable) for all inputs, we could potentially take the case where the input belongs to a smaller, restricted set.
- Parameterised Algorithms#tosee
- Heuristic approximations can be used to find a solution, with some error bound.