List Of NP-complete Problems
Here are some of the more commonly known problems that are NP-complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP-complete problems). Most of the problems in this list are taken from Garey and Johnson's seminal book Computers and Intractability: A Guide to the Theory of NP-Completeness, and are here presented in the same order and organization.
- This is an incomplete list, which may never be able to satisfy particular standards for completeness. You can help by expanding it with reliably sourced entries.
Read more about List Of NP-complete Problems: Mathematical Programming, Games and Puzzles, Computational Geometry, Miscellaneous
Famous quotes containing the words list of, list and/or problems:
“The advice of their elders to young men is very apt to be as unreal as a list of the hundred best books.”
—Oliver Wendell Holmes, Jr. (1841–1935)
“My list of things I never pictured myself saying when I pictured myself as a parent has grown over the years.”
—Polly Berrien Berends (20th century)
“Our [adult] children have an adult’s right to make their own choices and have the responsibility of living with the consequences. If we make their problems ours, they avoid that responsibility, and we are faced with problems we can’t and shouldn’t solve.”
—Jane Adams (20th century)