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

单词	NPcomplete
释义	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$ .
随便看	inverse function theorem InverseFunctionTheoremtopologicalSpaces inverse function theorem (topological spaces) InverseGaloisProblem inverse Galois problem InverseGudermannianFunction inverse Gudermannian function InverseImage inverse image InverseLaplaceTransformOfDerivatives inverse Laplace transform of derivatives InverseLimit inverse limit InverseNumber inverse number InverseOfAProduct inverse of a product InverseOfCompositionOfFunctions inverse of composition of functions InverseOfInverseInAGroup inverse of inverse in a group InverseOfMatrixWithSmallrankAdjustment inverse of matrix with small-rank adjustment InversesInRings inverses in rings