# NP-complete

A problem $\pi\in\mathcal{NP}$ is $\mathcal{NP}$ if for any $\pi^{\prime}\in\mathcal{NP}$ there is a Cook reduction of $\pi^{\prime}$ to $\pi$. Hence if $\pi\in\mathcal{P}$ then every $\mathcal{NP}$ problem would be in $\mathcal{P}$. A slightly stronger definition requires a Karp reduction or Karp reduction of corresponding decision problems as appropriate.

A search problem $R$ is $\mathcal{NP}$ hard if for any $R^{\prime}\in\mathcal{NP}$ there is a Levin reduction of $R^{\prime}$ to $R$.

Title NP-complete NPcomplete 2013-03-22 13:01:49 2013-03-22 13:01:49 Henry (455) Henry (455) 4 Henry (455) Definition msc 68Q15 NP complete NP hard NP-hard