a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are thousands of such problems known...

21 NP-complete problems are a set of computational problems which are NP-complete. In his 1972 paper, "Reducibility Among Combinatorial Problems", Richard...

NP-complete problems are the hardest of the problems to which solutions can be verified quickly. Somewhat more precisely, a problem is NP-complete when:...

decidable. NP-complete Class of decision problems which contains the hardest problems in NP. Each NP-complete problem has to be in NP. NP-easy At most...

opinion of this era." To attack the P = NP question, the concept of NP-completeness is very useful. NP-complete problems are problems that any other NP problem...

lists of problems: List of philosophical problems List of undecidable problems Lists of unsolved problems List of NP-complete problems List of PSPACE-complete...

technologies List of NP-complete problems List of paradoxes List of PSPACE-complete problems List of undecidable problems List of unsolved deaths Lists of problems...

complexity, strong NP-completeness is a property of computational problems that is a special case of NP-completeness. A general computational problem may have numerical...

complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which...

Here are some of the more commonly known problems that are PSPACE-complete when expressed as decision problems. This list is in no way comprehensive....

Intractability: A Guide to the Theory of NP-Completeness and Richard Karp's list of 21 NP-complete problems. The problems of finding a Hamiltonian path and a...

an appendix providing a thorough compendium of NP-complete problems (which was updated in later printings of the book). The book is now outdated in some...

the first problem that was proven to be NP-complete—this is the Cook–Levin theorem. This means that all problems in the complexity class NP, which includes...

circulations, spanning trees, matching, and matroid problems. For NP-complete discrete optimization problems, current research literature includes the following...

In complexity theory, the complexity class NP-easy is the set of function problems that are solvable in polynomial time by a deterministic Turing machine...

problem are hard. The clique decision problem is NP-complete (one of Karp's 21 NP-complete problems). The problem of finding the maximum clique is both fixed-parameter...

version of set covering is NP-complete. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972. The optimization/search version of set...

exact cover exists. The exact cover problem is NP-complete and is one of Karp's 21 NP-complete problems. It is NP-complete even when each subset in S contains...

co-NP. Any yes-instance for the original NP problem becomes a no-instance for its complement, and vice versa. An example of an NP-complete problem is...

3-SAT) is an NP-complete variant of the Boolean satisfiability problem. Given a conjunctive normal form with three literals per clause, the problem is to determine...

Computationally, the problem is NP-hard, and the corresponding decision problem, deciding if items can fit into a specified number of bins, is NP-complete. Despite...

subset of the integers sum to precisely T {\displaystyle T} . The problem is known to be NP-complete. Moreover, some restricted variants of it are NP-complete...

Many other problems in coding theory are also listed among the unsolved problems in mathematics. "P vs. NP – The Greatest Unsolved Problem in Computer...

states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic...

is one of Karp's 21 NP-complete problems. Knapsack problems appear in real-world decision-making processes in a wide variety of fields, such as finding...

with |M| ≥ k. This decision problem is known to be NP-complete; it is one of Karp's 21 NP-complete problems. It is NP-complete even in the special case that...

is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems. Suppose one has...

financial networks Fractional stable paths problems Fractional hypergraph matching (see also the NP-complete Hypergraph matching) Fractional strong kernel...

shown to be NP-complete by Opatrný (1979). The input to a betweenness problem is a collection of ordered triples of items. The items listed in these triples...

language L is in NP then the complement of L is in co-NP. (This does not mean that the complement of NP is co-NP—there are languages which are known to...