List of NP-complete Problems

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

Other articles related to "problem":

List Of NP-complete Problems - Miscellaneous
... Permutation generation Decoding of linear codes Shapley–Shubik power index Clustering problem Randomization test for matched pairs Maximum likelihood ranking Matrix domination Matrix cover Simply ...

Famous quotes containing the words list of, problems and/or list:

    Modern tourist guides have helped raised tourist expectations. And they have provided the natives—from Kaiser Wilhelm down to the villagers of Chichacestenango—with a detailed and itemized list of what is expected of them and when. These are the up-to- date scripts for actors on the tourists’ stage.
    Daniel J. Boorstin (b. 1914)

    I rarely speak about God. To God, yes. I protest against Him. I shout at Him. But to open a discourse about the qualities of God, about the problems that God imposes, theodicy, no. And yet He is there, in silence, in filigree.
    Elie Wiesel (b. 1928)

    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)