Home >  Term: NP-complete
NP-complete

The complexity class of decision problems for which answers can be checked for correctness, given a certificate, by an algorithm whose run time is polynomial in the size of the input (that is, it is NP) and no other NP problem is more than a polynomial factor harder. Informally, a problem is NP-complete if answers can be verified quickly, and a quick algorithm to solve this problem can be used to solve all other NP problems quickly.

0 0

Creator

  • GeorgeV
  •  (Gold) 1123 points
  • 100% positive feedback
© 2024 CSOFT International, Ltd.