NPComplete 2002-09-06 12:41:28 2002-09-06 12:41:28 Definition NP-hard % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here %\PMlinkescapeword{theory} A problem $\pi\in\mathcal{NP}$ is $\mathcal{NP}$ \emph{\PMlinkescapetext{complete}} 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 \emph{$\mathcal{NP}$ hard} if for any $R^\prime\in\mathcal{NP}$ there is a Levin reduction of $R^\prime$ to $R$.