= 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. \b[Membership in NP and NP-hardness are both required.]
Back to article page
