La teoria della complessita’ del calcolo: Un nuovo capitolo dell’algoritmica

The theory of complexity, a continuation of the theory of computability, investigates the number of operations and quantity of memory required to solve given problems. Problems can thus be classified as polynomial or non-polynomial (intractable) according to the quantity of resource required for their solution. The classNP-complete collects a number of problems polynomially reducible one to the other, for which no polynomial solution is known to exist.