Definition
is NP-hard if for every we have . If furthermore, , then we say is NP-complete.
NP-complete problems are the ‘hardest’ problems in NP. They are ‘as hard’ as any other NP problem.
Apr 10, 20261 min read
Definition
L⊆{0,1}⋆ is NP-hard if for every L′∈NP we have L′≤pL. If furthermore, L∈NP, then we say L is NP-complete.
NP-complete problems are the ‘hardest’ problems in NP. They are ‘as hard’ as any other NP problem.