Skip to interview prep
Apexed

55. Explain P, NP, NP-complete and NP-hard.

HardComplexity classes

Technical
Show model answer

P: problems solvable in polynomial time. NP: problems whose solutions can be verified in polynomial time. NP-complete: the hardest problems in NP; every NP problem reduces to them in polynomial time (examples: SAT, 3-colouring, subset sum, the decision version of the travelling salesman problem). NP-hard: at least as hard as NP-complete problems, but not necessarily in NP (for example optimisation versions or the halting problem).

Whether P = NP is unknown. In practice, for NP-hard problems use approximation algorithms, heuristics, or exact algorithms on small inputs.

Explain P, NP, NP-complete and NP-hard. — Data structures & algorithms interview question — Apexed