About
- Tractable: a problem that can be solved in polynomial time
- intractable: a problem that can NOT be solved in polynomial time
Articles Related
Type
Tractable
the problems that can be solved by a computer using no more time than some slowly growing function of the size of the input are called tractable
Intractable
- Problems that (appear to) require exponential time.
- NP-completeness and beyond.
intractability: Solvable Problems but with an exponential time in the input size.
The solution must then be approximated.
While the undecidable problems have been proved not to have any solution, for the intractable problems we have very strong evidence that they require exponential time, but no proof.