Formal definition of NP Def.A language L∈{0，l}*is in NP if there exists a polynomial p:N->N and a polynomial- time Turing machine M such that for every x E {0,1}*, xeL台]u∈{0,1plxs.t.M(x,u)outputs1 M:the verifier for L. For xe L,the u on the RHS is called a certificate for x(with respect to the language L and machine M). So NP contains those problems easy to check.Formal definition of NP ◼ Def. A language 𝐿 ⊆ 0,1 ∗ is in NP if there exists a polynomial 𝑝: ℕ → ℕ and a polynomial￾time Turing machine 𝑀 such that for every 𝑥 ∈ 0,1 ∗ , 𝑥 ∈ 𝐿 ⇔ ∃𝑢 ∈ 0,1 𝑝 𝑥 𝑠.𝑡. 𝑀(𝑥, 𝑢) outputs 1 ◼ 𝑀: the verifier for 𝐿. ◼ For 𝑥 ∈ 𝐿, the 𝑢 on the RHS is called a certificate for 𝑥 (with respect to the language 𝐿 and machine 𝑀). ◼ So NP contains those problems easy to check. 4