The Free On-line Dictionary of Computing (30 December 2018):

NP-complete

    (NPC, Nondeterministic Polynomial time complete)
   A set or property of computational decision problems which
   is a subset of NP (i.e. can be solved by a
   nondeterministic Turing Machine in polynomial time),
   with the additional property that it is also NP-hard.  Thus
   a solution for one NP-complete problem would solve all
   problems in NP.  Many (but not all) naturally arising problems
   in class NP are in fact NP-complete.

   There is always a polynomial-time algorithm for transforming
   an instance of any NP-complete problem into an instance of any
   other NP-complete problem.  So if you could solve one you
   could solve any other by transforming it to the solved one.

   The first problem ever shown to be NP-complete was the
   satisfiability problem.  Another example is Hamilton's
   problem.

   See also computational complexity, halting problem,
   Co-NP, NP-hard.

   (http://fi-www.arc.nasa.gov/fia/projects/bayes-group/group/NP/).

   [Other examples?]

   (1995-04-10)