NP-complete

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

A search problem $R$ is $\mathrm{N}\mathit{}\mathrm{P}$ hard if for any $R^{\prime }\in 𝒩𝒫$ there is a Levin reduction of $R^{\prime }$ to $R$.