Source : Free On-Line Dictionary of Computing

NP-complete
     
         (NPC, Nondeterministic Polynomial time complete)
        A set or property of computational {decision problem}s 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)