Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 38 / 4 / a / Solution

P is the class of decision problems decided by a deterministic algorithm in time polynomial in the encoded input length. NP is the class whose yes-instances have complexity certificates of polynomial length that a deterministic algorithm verifies in polynomial time.

A decision problem is NP-complete if it belongs to NP and is NP-hard: every problem in NP admits a polynomial-time many-one reduction to it. Such a reduction maps an instance $I$ to an instance $R(I)$ in polynomial time and satisfies $I$ is a yes-instance if and only if $R(I)$ is a yes-instance. Membership in NP and NP-hardness are both required.