All currently known NP-complete problems remain NP-complete even under much weaker reductions.
Într-adevăr, problemele NP-complete cunoscute în prezent rămân probleme NP-complete chiar și cu reduceri mult mai slabe.