NP (kompleksitet)

NP er ei kompleksitetsklasse som beskriver beslutningsproblemer. Det finnes flere definisjoner hvor alle er like gyldige. En definisjon på det er at ei løsning skal kunne verifiseres i polynomiell tid. Sagt annerledes vil det si at det finnes ei deterministisk turingmaskin som kan bekrefte at det er en del av språket i polynomiell tid. Språket beskrives som problemet. En annen definisjon på det er at NP er mengda over alle beslutningsproblemer som kan løses av ei ikke-deterministisk turingmaskin som kjører i polynomiell tid. Disse to nevnte definisjonene er bevist er ekvivalente.

Eulerdiagram for kompleksitetsklassene P, NP, NP-komplett, og NP-hardt. Under antagelsene om at henholdsvis P≠NP og P=NP.

Eksempler

P er inneholdt i kompleksitetsklassen NP. Det betyr at ethvert problem løsbart i polynomiell tid er også en del av NP.

Eksempler på problemer i NP som ikke er med P er delmengdesumproblemet. Det er også et NP-komplett problem. Problemet kan riktig nok løses i pseudopolynomiell tid ved bruk av dynamisk programmering, men det er fortsatt inga løsning på problemet i deterministisk polynomiell tid med mindre kompleksitetsklassene NP og P er like, som fortsatt er et stort spørsmål i matematikken som per dags dato ikke er et bevis for.

Delmengdesumproblemet går ut på at gitt ei mengde av heltall skal man bestemme om det finnes ei delmengde som er slik at summen av alle elementene er 0. I mengda {−2, −3, 15, 14, 7, −10} vil for eksempel delmengda {−2, −3, −10, 15} summere til 0. Problemet har altså en polynomiell tid verifikator da det kun trengs 3 addisjoner for å verifisere at denne delmengda summerer til 0. For å se problemet i fra den andre definisjonen kan man la ei turingmaskin ikke-deterministisk velge ei delmengde og sjekke om denne summerer til 0 i ikke-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 Problems), pp. 241–271.