In 1972, Richard Karp proved that several other problems were also NP-complete (see Karp's 21 NP-complete problems); thus there is a class of NP-complete problems (besides the Boolean satisfiability problem).
În 1972, Richard Karp a demonstrat că sunt mai multe alte probleme NP-complete (a se vedea cele 21 de probleme NP-complete ale lui Karp); astfel, există o clasă de probleme NP-complete (pe lângă problema satisfiabilități booleene).