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$.

Title	NP-complete
Canonical name	NPcomplete
Date of creation	2013-03-22 13:01:49
Last modified on	2013-03-22 13:01:49
Owner	Henry (455)
Last modified by	Henry (455)
Numerical id	4
Author	Henry (455)
Entry type	Definition
Classification	msc 68Q15
Synonym	NP complete
Synonym	NP hard
Defines	NP-hard