NP-hard
Defined in 2 lectures. Each definition is in that lecture's terms.
Definitions are written by AI from each lecture’s transcript. The time opens the lecture where the lecturer explains it.
- Problems that are at least as hard as the hardest problems in NP, meaning no polynomial-time algorithm is known for them.
- A problem is NP-hard if every problem in NP reduces to it in polynomial time.