Tractable / Intractable Problem

1 - About

Algorithm - Problem

3 - Type

3.1 - 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

3.2 - 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.

Data Science
Data Analysis
Data Science
Linear Algebra Mathematics

Powered by ComboStrap