NP-hardt

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.

Eulerdiagram for kompleksitetsklassene P, NP, NP-komplett, og NP-hardt. Under føresetnadane om at høvesvis P≠NP og P=NP.

Døme

Eit døme på eit NP-hardt problem kan vera eit NP-komplett problem. Eit velkjent problem er handelsreisandeproblemet som går ut på å finna kortaste veg som går gjennom ei gjeven mengde nodar.

Eit problem som ikkje er NP-komplett men som er NP-hardt er stoppeproblemet. Stoppeproblemet går ut på om ein kan avgjera om eit gjeve program med ein gjeven input vil stoppa eller ikkje. Dette er eit problem som ikkje er turingavgjerbart. Det finst inga turingmaskin som vil kunna avgjera 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.