If we have an algorithm that need to run $n=2$ operations and then halt, I think we could say the problem it solves, is tractable, but if $n=10^{120}$ althought It could be theoretically solvable it seems to be intractable, and what about a problem that needs $n=10^{1000}$, or $n=10^{10^{1000}}$ operations, that's seems an intractable problem for sure.

Then we see there is a k, from which $n\ge k$ operations problems are intractable, and $n\lt k$ are tractable ones.

I doubt about that k to exist.. Where is the limit? Can a Technological advance turn some intractable problems for a given n into a tractable ?

I would like to read your opinion.


I think this question is similar as asking if Church–Turing thesis is correct, because if the difference about solving a computable problem in a Turing Machine and in any other Turing Complete Machine, is "only a constant" about the number of operations, then I think that asking about computable is the same as asking about effective calculability.. Now I see tractable means polynomial time, and inctractable is related with no polynomial time solution. But the difference between two machines, for the same (even tractable) problem, is about Church-Turing thesis.

  • 4
    $\begingroup$ What is "tractable" depends on how much time you have for the task. An algorithm two seconds may be great (planning a route) or catastrophic (controlling car brakes). It is not at all clear what "intractable" means in your question. $\endgroup$ – Raphael Jun 17 '12 at 13:13
  • $\begingroup$ @Raphael That practical ambiguity is what makes me wonder about theory.Meaning of 'intractable' within complexity theory, specifically, could it have a general definition?. If there were not any general constant $n\ge k$, to label a problem as intractable,so I think talk about "efficient computing" would has no meaning either.So perhaps, guessing a general k,could be incomputable..Is this related with P != NP problem as much as Cobham's thesis relate tractable with P problems?. As Dmitri say "the notion of intractability does not apply to specific one-off problems", that's why I ask this. $\endgroup$ – Hernan_eche Jun 28 '12 at 4:32
  • $\begingroup$ I don't thionk such a fixed $k$ is a good approach to define "tractable". First, it is too specific to a given situation. Second, some problems can be solved in parallel, yielding different $k$ yet again. I don't think a precise definition of "tractable" is needed; it is an informal way to describe problems solvable in a given class of settings with some properties. $\endgroup$ – Raphael Jun 28 '12 at 11:31

Intractability is a graphical metaphor for a notion related to asymptotic complexity.

Let me remind that in abstract terms a computational problem is to find given an input $s$ a solution $r$ to an instance of the problem specified by $s$.

A problem is tractable if for every input $s$ of size $n$ a solution can be found with a number of operations bounded by a certain slowly growing function $P(n)$. The definition of slow growth is not important at this stage. Let us agree that a linear function is slowly growing and an exponential $e^n$ is not slowly growing.

If no such slowly growing upper bound exists, we have to admit that the problem is intractable. That is for any improvement in computer technology we can slightly increase the size of the input to render the effect of this improvement to zero.

Thus the precise meaning of the notion of intractability is that it stands against any technological advance.

It is important to note that there is no concrete integer number that characterizes intractability. It is the rate of growth that makes a problem intractable.

If instead you look at a specific question like solving the game of chess, you cannot say that it is intractable since as soon as it is solved once the problem will become trivial. Thus the notion of intractability does not apply to specific one-off problems whatever be the number of operations that a particular algorithm to solve them takes.

Here is a final remark to check your understanding.

An algorithm is called efficient if it efficiently solves every instance of some computational problem. If for some instance it takes this efficient algorithm $10^{20}$ operations to complete, a trivial algorithm that simply reproduces the solution once produced by an efficient algorithm will beat the efficient algorithm to this problem. Yet this trivial algorithm will fail at any instance of the problem that was not previously seen.

  • $\begingroup$ thanks I think I understand it better, I still have a question about this:*"If no such slowly growing upper bound exists, we have to admit that the problem is intractable.". Imagine an example of a program, a thought experiment, where $P(n)$ is not a monotonic function of n, so an input of size n=10, could take $10^{100^{n}}$ operations, *but for every input of size $n\gt10$ or $n\lt10$ could take exactly $2*n$ ops then the function for the upper bound exist but is strange enough for single values of n, then the notion of intractability would apply to specific one-off problems? $\endgroup$ – Hernan_eche Jun 16 '12 at 16:27
  • 1
    $\begingroup$ @Hernan_e thank you, this is a very good point. Phenomena similar to what you describe are known in complexity theory. That is when difficulty of problem instances depends on a certain parameter in a non-monotonic fashion. Such difficult instances are often referred to as hard instances. To avoid confusion the notion of intractability is not applied. $\endgroup$ – Dmitri Chubarov Jun 16 '12 at 17:07
  • 1
    $\begingroup$ @Hernan_e: If you have an algorithm which takes 10^(100^10) operations for n=10 and 2n operations for n≠10, then it is still a linear-time algorithm with a huge coefficient (do you see why?). Moreover, if the input size means the number of bits needed to specify the input, you can reduce this coefficient to something non-huge by hard-coding the answers to all the instances with n=10, because there are only finitely many instances with n=10. $\endgroup$ – Tsuyoshi Ito Jun 17 '12 at 0:43
  • 2
    $\begingroup$ This answer deals with the notion of "intractable" as used in complexity theory. What the word means in more applied contexts let alone practice is completely different. For example, in bioinformatics some problems require sub-linear algorithms, otherwise they run too long. $\endgroup$ – Raphael Jun 17 '12 at 13:16
  • 1
    $\begingroup$ @Hernan_e as Raphael commented above the word "intractability" is not confined to complexity theory in other contexts it is used to refer to problems that are simply beyond the capabilities of present computers. In that sense intractability is a rapidly moving target as methods that were impractical before or problems that were beyond reach become amenable to modern computers. Yet there are problems where the progress is very slow. From the top of my head I would name Kaplansky conjecture on group rings. $\endgroup$ – Dmitri Chubarov Jun 19 '12 at 14:34

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.