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).
- 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) ?