NP-completeness NP-completeness:A language L is NP- complete if OL∈NP VL'E NP,L'is reducible to L in polynomial time. ■ Such problems L are the hardest in NP. Once you can solve L,you can solve any other problem in NP. NP-hard:any NP language can reduce to it. i.e.satisfies 2nd condition in NP-completeness def. 14NP-completeness ◼ NP-completeness: A language 𝐿 is NP￾complete if ❑ 𝐿 ∈ 𝐍𝐏 ❑ ∀𝐿 ′ ∈ 𝐍𝐏, 𝐿 ′ is reducible to 𝐿 in polynomial time. ◼ Such problems 𝐿 are the hardest in NP. ◼ Once you can solve 𝐿, you can solve any other problem in NP. ◼ NP-hard: any NP language can reduce to it. ❑ i.e. satisfies 2nd condition in NP-completeness def. 14