NP-complete


A problem π∈𝒩⁢𝒫 is 𝒩⁢𝒫 if for any π′∈𝒩⁢𝒫 there is a Cook reduction of π′ to π. Hence if π∈𝒫 then every 𝒩⁢𝒫 problem would be in 𝒫. A slightly stronger definition requires a Karp reduction or Karp reduction of corresponding decision problemsMathworldPlanetmath as appropriate.

A search problem R is N⁢P hard if for any R′∈𝒩⁢𝒫 there is a Levin reduction of R′ 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