NP i kompleksitetsteori

NP er ei kompleksitetsklasse som skildrar beslutningsproblem. Det finst fleire definisjonar av NP som alle er like gyldige. Ein definisjon på NP er at det er mengda over problem som har ei løysing som kan verifiserast i polynomiell tid. Sagt på ein annan måte vil det si at det finst ei deterministisk turingmaskin som kan stadfesta at det er ein del av språket i polynomiell tid. Språket vert skildra som problemet. Ein annan definisjon på det er at NP er mengda over alle beslutningsproblem som kan løysast av ei ikkje-deterministisk turingmaskin som køyrer i polynomiell tid. Desse to nemnde definisjonane er ekvivalente.

Døme

Kompleksitetsklassa P er innehalden i kompleksitetsklassa NP. Det tyder at kvar og eit problem som kan løysast i polynomiell tid er òg ein del av NP.

Døme på problem i NP som ikkje er med P er delmengdesumproblemet. Det er òg eit NP-komplett problem. Problemet kan rett nok løysast i pseudopolynomiell tid ved bruk av dynamisk programmering, men det er enno inga løysing på problemet i deterministisk polynomiell tid med mindre kompleksitetsklassene NP og P er like, som enno er eit stort spørsmål i matematikken som per dags dato ikkje er eit bevis for.

Delmengdesumproblemet går ut på at gjeve ei mengde av heiltal skal ein avgjera om det finst ei delmengde som er slik at summen av alle elementa er 0. I mengda {−2, −3, 15, 14, 7, −10} vil til dømes delmengda {−2, −3, −10, 15} summera til 0. Problemet har altså ein polynomiell-tid verifikator då det berre vert nødvendig med 3 addisjonar for å verifisera at denne delmengda summerer til 0. For å sjå problemet i frå den andre definisjonen kan ein la ei turingmaskin ikkje-deterministisk velja ei delmengde og sjekka om denne delmengda summerer til 0 i ikkje-deterministisk polynomiell tid.

Litteratur

Sipser, M. (1996), Introduction to the Theory of Computation, Sections 7.3–7.5 (The Class NP, NP-completeness, Additional NP-complete Problem sitt), pp. 241–271.