We attempt to find the best algorithms possible to simplify problems that would otherwise take an enormously long time to calculate and despite the fact that CPU speeds are drastically increasing as described in Moores Law (double CPU speed every eighteen months), it may take some time yet for us to get a clear view of where were heading; and the question remains: Can we always find an algorithm to solve any type of problems?.
I think it would be fair to say that with the machines that we have now, the answer is a plain no. But who knows what the future holds? With the endless possibilities that Quantum Computing seems to have to offer, these problems that seem so intractable now could be solved without too much trouble in the not-too-distant future.
For now at least, what can we solve? Well, the algorithms that are devised to solve todays problems are separated into two distinct types: tractable and intractable. Tractable algorithms have a complexity that can be solved fairly quickly by todays machines. The complexity of a problem is measured by the most efficient solution to it. It is widely accepted that any problem that is decidable within polynomial time is tractable. .
Sometimes however, this is not the case. There are circumstances when a polynomial-time algorithm may not be efficient enough or when an exponential algorithm will suffice, or in fact, in between: such as a problem with a complexity of eO(2^( an)). You would tend to think that it is intractable just because it has a power sign on it. But then again, the increment to this when the values of n is increased, is very minimal.
Finally, I would like to conclude that I think the limits of computation are endless. In the case of complexity, I think faster machines are still quite a long way off and that for now, we just have to hope that better algorithms are devised in order to tackle this problem. There may be new issues raised about complexity if indeed we do get to the point where we can say that the tractability of problems could be ignored because the machines in operation would be able to handle any complexity; whether it be linear, or in fact exponential.
