NP-hardt
From Wikipedia, the free encyclopedia
De NP-harde problemene er en mengde problemer som er minst like harde som de hardeste problemene i NP. Sagt på en annen måte, hvis ethvert problem i NP kan polynomtidsreduseres til et gitt problem H, er problemet H NP-hardt. Hvis H også er med i NP, vil det bety at H er et av de hardeste problemene som eksisterer i NP. H kalles da NP-komplett i tillegg til NP-hardt. En konsekvens er at om man skulle finne en polynomtidsalgoritme for et eller annet NP-hardt problem, vil alle problemer i NP kunne løses i polynomiell tid.