A comparsion between different approaches to the classification of NP-complete problems is presented. New results about the classification of the problems and the characterization of the reductions are given. Formalizations of technics used in pratice when studying properties of a specific problem are also introduced.

DOI Code:

Full Text: PDF

Creative Commons License
This work is licensed under a Creative Commons Attribuzione - Non commerciale - Non opere derivate 3.0 Italia License.