# Definition(s)/characterization(s) of intractability

I've been searching around for definitions of intractability, and I realized that despite being widely used, the concept of intractability (when talking about computing problems of course) is not formally defined.

I'm currently writing a report in which I characterize some problems as intractable (in my context, they are intractable because their output size can be exponential w.r.t the input size), and I need to feel 'comfortable' about what intractability is in order to write coherent stuff in the report.

The way I understood it is the following: a problem is intractable if it cannot be solved reasonably fast, with reasonably big instances.

This leaves a lot of space for human appreciation of what a reasonable execution time is, and what a reasonable input size is. This also allows to describe some problems in P as intractable (if it runs in O(n^150) for instance) , and even in some cases, to eventually describe some NP-complete problems as tractable (many MILP problems can actually be solved fast with reasonably big instances).

My questions:

• Is there a better/more elegant/more precise way to define intractability ?
• Are there problems/contexts which could be described as being on the border, meaning that they're really not easily fitting in any of the 2 categories (tractable/intractable) ?
• I'm not quite sure what you mean by 'with reasonably big instances'. Do you mean that you consider a problem intractable if we cannot quickly solve some reasonably large instances, all reasonably large instances, or some other set of reasonably large instances? – Discrete lizard Jun 6 '19 at 9:52
• @Discretelizard good question ! I left this part open because it was open in most of the definitions I came across. It seems that solving a problem quick enough on most instances, or solving it quick enough in average, can be enough to qualify for tractability. For instance, I would consider the simplex algorithm as tractable in general, despite it not being in P. – m.raynal Jun 6 '19 at 13:24

This means that, if you are using run-of-the-mill TMs, then the class of tractable problems is $$\mathbf{P}$$. If you use probabilistic TMs (with two-sided error), it would then be $$\mathbf{BPP}$$. If you use quantum circuits, $$\mathbf{QBP}$$. For ATMs, $$\mathbf{PSPACE}$$—and so on.
The way tractability is usually understood, this is impossible. There is a well-defined set of tractable problems. Using standard logic, a problem is either in that set or it isn't. You could identify some problems as more difficult than others, but that is a different concept altogether since it would produce a whole spectrum of hardness (and, hence, is not quite captured by the aforementioned notion of tractability). What would rather fit that notion is time complexity itself; after all, it allows you to express a problem's hardness based on the time resources (as a function on $$\mathbb{R}_0$$) needed to solve it. (And, as we know, most such functions can be compared using, for instance, asymptotic analysis.)
TL;DR: Intractability is a discrete concept; time complexity is a continuous one (or as continuous as it can be in the set of (computable) $$\mathbb{N} \to \mathbb{R}_0$$ functions).