62
edits
Changes
Jump to navigation
Jump to search
Creating page. Sadly, I'm not qualified enough to give extensive comments.
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.
* 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.