Lattice Theoretic Ordering Properties for NP-Complete Optimization Problems
Giorgio Ausiello, Alessandro D’Atri, Marco Protasi · Fundamenta Informaticae · 1981
The ordering among classes of isomorphic NP-complete optimization problems is studied from a lattice theoretic point of view. It is shown that the set of such classes has the structure of an upper semilattice; while a top element can found be it is proved that no bottom element can exist.