Hopp til innhold

NP-hardt

Fra Wikipedia, den frie encyklopedi
Eulerdiagram for kompleksitetsklassene P, NP, NP-komplett, og NP-hardt. Under antagelsene om at henholdsvis P≠NP og P=NP.

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.

Eksempler

[rediger | rediger kilde]

Et eksempel på et NP-hardt problem kan være et NP-komplett problem. Et velkjent problem er handelsreisendeproblemet som går ut på å finne korteste vei som går gjennom ei gitt mengde noder.

Et problem som ikke er NP-komplett, men som er NP-hardt er stoppeproblemet. Stoppeproblemet går ut på om man kan avgjøre om et gitt program med et gitt input vil stoppe eller ikke. Dette er et problem som ikke er turingavgjørbart. Det finnes inga turingmaskin som vil kunne avgjøre problemet.

Litteratur

[rediger | rediger kilde]