[Solved]: Which is the minimal number of operations for intractability?

Problem Detail: 

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.

EDIT

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.

Asked By : Hernan_eche

Answered By : Dmitri Chubarov

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2385

3.2K people like this

 Download Related Notes/Documents