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 8 Certificate for sat would be an assignment 8 Certificate for hamiltonian Cycle would be a sequence of n vertices, V1, V2, .. ,VnAn 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