An Equivalent Definition of Class NP Class NP:Problems checkable or verifiable in polynomial time Verification: *Given a "certificate"of a solution,we could verify that the certificate is correct,e.g. Certificate for SAT would be an assignment Certificate for Hamiltonian Cycle would be a sequence of n vertices,V1,V2,...Vn 8An Equivalent Definition of Class NP Class NP: Problems checkable or verifiable in polynomial time Verification: ❖Given a “certificate” of a solution, we could verify that the certificate is correct, e.g. ❖Certificate for SAT would be an assignment ❖Certificate for Hamiltonian Cycle would be a sequence of n vertices, v1 , v2 , …, vn 8