Saturday, September 29, 2007

Algorithms and Computing power

While talking about Algorithms, we mostly care about time and space complexity. we try to analyze a given algorithm by figuring out how fast it runs and how much time it takes. Depending on the time factor we classify the problems into one of the complexity classes (P, NP , NP-Complete or NP-Hard). We claim that algorithms which can solve problems, in polynomial time in the size of their inputs (ie P class of problems) are tractable. we worry a lot if a problem takes exponential time. We have lots of great brains working out to solve several hard problems in polynomial time or atleast get a feasible solution algorithm in polynomial time. Now when Moore's law is still holding good and when Intel and other chip makers envision tera computing, would the complexity theory go extinct ? I mean if our processors could crunch trillions of numbers and operations / sec, would we still classify problems on polynomial time ? Agreed that we cant take growth in processing power for granted but I am sure that advancements in computing power will greatly influence the way we define, analyze and solve problems.

No comments: