Npcomplete

1 definition found

From The Free On-line Dictionary of Computing (27 SEP 03) [foldoc]:

  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)