- 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.