NP-co Problems

NP-complete problems refer to decision problems.

Eg: set cover problem. The decision version of set covering is NP-complete, and the optimization version of set cover is NP-hard.
http://en.wikipedia.org/wiki/Set_cover_problem



Why the reduction started from CIRCUIT-SAT?

is CIRCUIT-SAT meaningful? useful?


The concept of NP-complete was introduced by Stephen Cook(Turing receiver)in 1971. In 1972, Richard Karpg (Turing receiver) proved that several other problems were also NP-complete (see Karp's 21 NP-complete problems);





Dominating Set Problem:
http://en.wikipedia.org/wiki/Dominating_set_problem

Karp's 21 NP-complete problems:

http://en.wikipedia.org/wiki/Karp's_21_NP-complete_problems


List of NP-complete problems:

http://en.wikipedia.org/wiki/List_of_NP-complete_problems