NP-hardt

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

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

• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.