Blog

Your dream job? Lets Git IT.
Interactive technical interview preparation platform designed for modern developers.

XGitHub

Platform

  • Categories

Resources

  • Blog
  • About the app
  • FAQ
  • Feedback

Legal

  • Privacy Policy
  • Terms of Service

© 2025 LetsGit.IT. All rights reserved.

LetsGit.IT/Categories/Algorithms
Algorithmshard

NP-hard vs NP-complete: what's the difference?

Tags
#complexity-theory#np-hard#np-complete#reductions
Back to categoryPractice quiz

Answer

NP-complete problems are both in NP (a solution can be verified in polynomial time) and NP-hard. NP-hard means “at least as hard as NP problems” but it might not be in NP (e.g., optimization versions). If any NP-complete problem has a polynomial-time algorithm, then P = NP.