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)
“Thirty—the promise of a decade of loneliness, a thinning list of single men to know, a thinning brief-case of enthusiasm, thinning hair.”
—F. Scott Fitzgerald (1896–1940)
“If combat means living in a ditch, females have biological problems staying in a ditch for 30 days because they get infections.... Males are biologically driven to go out and hunt giraffes.”
—Newt Gingrich (b. 1943)