Tractable / Intractable Problem


Algorithm - Problem



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


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

Powered by ComboStrap