Encyclopedia > K > Karp's 21 NP-complete problems
Karp's 21 NP-complete problems
One of the most important results of computational complexity theory was Stephen Cook's 1971 paper that demonstrated the first NP-complete problem, the boolean satisfiability problem. In 1972, Richard Karp took this idea a leap forward with his landmark paper, “Reducibility Among Combinatorial Problems”, in which he showed that 21 diverse combinatorial and graph theoretical problems, each infamous for their intractability, were all NP-complete.
Information are taken from Wikipedia, the open encyclopedia, to which contribute many volunteers from around the whole world. Texts are available under the following conditions GNU Free Documentation License.
Encyklopedie (cz) Encyklopédia (sk) Enzyklopädie (de)