Questions related to NP-hardness and NP-completeness.

In complexity theory, NP-hard problems are, informally speaking, problems which are at least as hard as all problems in NP. Difficulty of problems is compared by constructing reductions from one problem to the other.

NP-hard problems which themselves belong to NP are called NP-complete problems. More informally, NP-complete problems are the hardest problems in NP.

history | excerpt history