2
$\begingroup$

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) ?
$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Discrete lizard Jun 6 '19 at 9:52
  • $\begingroup$ @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. $\endgroup$ – m.raynal Jun 6 '19 at 13:24
2
$\begingroup$

What is intractable or not inherently depends on what the underlying computational model is as well as what your conventions are. By far, the most widely used notion is based on the Cobham-Edmonds thesis, which states that, for any given machine model for which time (or any equivalent thereof) is a valid resource, the tractable problems are those that can be solved in polynomial time. In this sense, tractability quite certainly has a formal definition.

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.

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

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.