Beslutningsproblemer

Beslutningsproblemer er problemstillinger der svaret er enten ja eller nei. Formelt kan et beslutningsproblem ses som et språk L over et alfabet Σ, der hver inngangsstreng w ∈ Σ* representerer et eksempel av problemet, og spørsmålet er om w tilhører L. Hvis det finnes en beregningsprosedyre (en algoritme) som for alle innganger avgjør riktig ja/nei, sies problemet å være decidable (besluttelig).

Eksempler på beslutningsproblemer inkluderer SAT (er en gitt booleansk formel satisfierbar?), primalitetstest (er et tall et primtall?), og spørsmål om grafers egenskaper som sammenhengende eller ruteoppdagelse. Halteproblemet, som spør om et gitt program vil stoppe på en gitt input, er et berømt eksempel på et ubesluttelig beslutningsproblem.

Beslutningsproblemer skilles ofte fra andre typer problemer som optimalisering og søk. Innenfor beregnings- og kompleksitetsteori studeres hva som gjør et beslutningsproblem besluttbart, og hvor effektivt det kan løses. Viktige begreper er tidskompleksitet og plassbruk, samt klassene P (løses i polynomiell tid) og NP (snitt av problemer der ja-instansen kan bekreftes i polynomiell tid). NP-kompletthet viser problemer som er minst like harde som de vanskeligste problemer i NP, hvor SAT er et klassisk eksempel. Reduksjoner brukes til å sammenligne problemer ved å vise at løsning av ett problem kan omgjøres til løsning av et annet i polynomisk tid.

Beslutningsproblemer er sentrale i forskning og anvendes i datasikkerhet, programverifikasjon, algoritmedesign og språkteori. Historisk knyttes de til Hilberts Entscheidungsproblem og senere arbeid av Turing, Church og Cook–Levin-teoremet.