NP-hardt
From Wikipedia, the free encyclopedia
Dei NP-harde problema er ei mengde problem som er minst like harde som dei hardaste problema i NP. Sagt på ein annan måte, viss kvart problem i NP kan polynomtidsreduserast til eit gjeve problem H, er problemet H NP-hardt. Viss H òg er med i NP, vil det tyda at H er eit av dei hardaste problema som eksisterer i NP. H vert då kalla NP-komplett i tillegg til NP-hardt. Ein konsekvens er at om ein skulle finna ein polynomtidsalgoritme for kvart og eit NP-hardt problem, vil alle problem i NP kunna løysast i polynomiell tid.