When is an algorithm feasible? Soft computing approach
Hung Tan Nguyen, Владик Крейнович · 2002
Not all algorithms are feasible (=physically possible, either now or in the future). For example, an algorithm that requires 2 to the power 2/sup n/ computational steps for an input of length n will (for reasonable inputs) take time that is exponentially longer than the lifetime of the Universe. So, if we are interested in separating doable algorithms from purely theoretical ones, we must have a formal notion of a feasible algorithm. Now, the most widely accepted formal description of this notion is an algorithm that can be computed in polynomial time. However, the majority of researchers agree that it is only a good approximation to actual feasibility: e.g., an algorithm that requires 10/sup 10000000000/n computational steps is time-polynomial but hardly feasible. In the present paper, we formalize the idea of Zadeh and describe feasibility as a fuzzy notion. The resulting definition of feasibility is more adequate than the existing ones: e.g., in the new definition, it is no longer true that all time-polynomial algorithms are feasible.>