Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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.