catflap.org Online Dictionary Query

  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/)" rel="nofollow">(http://fi-www.arc.nasa.gov/fia/projects/bayes-group/group/NP/).
       
          [Other examples?]
       
          (1995-04-10)
       
       

  NP-complete
     a.
     (lb en computing theory of a decision problem) That is both NP
  (solvable in polynomial time by a non-deterministic Turing machine) and
  NP-hard (such that any (other) NP problem can be reduced to it in
  polynomial time).

  NP-complete
     a.
     (lb en computing theory of a decision problem) That is both NP
  (solvable in polynomial time by a non-deterministic Turing machine) and
  NP-hard (such that any (other) NP problem can be reduced to it in
  polynomial time).

  NP-complete
     a.
     (lb en computing theory of a decision problem) That is both NP
  (solvable in polynomial time by a non-deterministic Turing machine) and
  NP-hard (such that any (other) NP problem can be reduced to it in
  polynomial time).

  NP-complete
     a.
     (lb en computing theory of a decision problem) That is both NP
  (solvable in polynomial time by a non-deterministic Turing machine) and
  NP-hard (such that any (other) NP problem can be reduced to it in
  polynomial time).

  NP-complete /ˌɛnpˈiː kəmplˈiːt/
  NP-vollständig  [math.]

  NP-complete /ˌɛnpˈiː kəmplˈiːt/ 
  NP-täydellinen
  both NP and NP-hard