# NP-complete

A problem $\pi \in \mathcal{N}\mathcal{P}$ is $\mathcal{N}\mathcal{P}$ if for any ${\pi}^{\prime}\in \mathcal{N}\mathcal{P}$ there is a Cook reduction of ${\pi}^{\prime}$ to $\pi $. Hence if $\pi \in \mathcal{P}$ then every $\mathcal{N}\mathcal{P}$ 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 *$\mathrm{N}\mathit{}\mathrm{P}$ hard* if for any ${R}^{\prime}\in \mathcal{N}\mathcal{P}$ 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 |