Introduction

Abstract

En
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.