dict.org

The DICT Development Group


Search for:
Search type:
Database:

Database copyright information
Server information


1 definition found
 for NP-complete
From 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/)">(http://fi-www.arc.nasa.gov/fia/projects/bayes-group/group/NP/).
  
     [Other examples?]
  
     (1995-04-10)
  

Contact=webmaster@dict.org Specification=RFC 2229