Difference between revisions of "NP-complete"
Jump to navigation
Jump to search
(Creating page. Sadly, I'm not qualified enough to give extensive comments.) |
m (Cat) |
||
| Line 6: | Line 6: | ||
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. | 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. | ||
| + | |||
| + | [[Category:Computers]] | ||
Revision as of 13:21, December 3, 2008
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.