Tractability

It is time now to discuss one big theoretical application of all our theory. Consider we're given a problem $\Phi$. There are three outcomes to solving this problem. Firstly, $\Phi$ might not have a solution. Secondly, our problem might have a solution in P. Lastly, our solution might be NP-HARD.

It's the last case we're interested in. When we know that a problem is in P, then we say that it is tractable. When we know it's NP-HARD, we say it's intractable. These problems effectively may not have solutions at all. They are just too hard to solve. So, we have to begin looking at solving them sub-optimally.