From Conservapedia
Jump to: navigation, search

NP-complete is a complexity class in computer science. The NP is short for "nondeterministic polynomial," and the term is used to refer to a class of problems with the following properties:

  • Solutions to NP-complete problems can be verified in polynomial time.
  • If a polynomial-time solution to one NP-complete problem is found, then every other NP-complete problem can be solved in polynomial time.
  • As implied by the above two, fast (i.e. polynomial time) solutions do not exist as of yet.

Because there are many NP-complete problems which have strong implications in physics, biology and other areas of science, much work in computer science is devoted toward developing algorithms which yield approximate solutions to these problems.