Beslutsproblem

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2019-10) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Inom datavetenskapen, och särskilt komplexitetsteori är ett beslutsproblem ett beräkningsproblem som ska besvaras med ja eller nej.

Ett exempel på ett beslutsproblem är: kan man rita den här figuren utan att lyfta pennan? Detta problem kallas i matematiken för att hitta en Eulerstig. Märk att själva lösningen i ett beslutsproblem, i exemplet hur man ritar figuren, inte är intressant. Avsikten är att förenkla och formalisera beräkningsproblem så att man kan resonera om dem på ett matematiskt sätt. Har man väl en algoritm som löser ett beslutsproblem brukar det inte vara svårt att anpassa den till att plocka fram lösningen.

Se även

• Optimeringsproblem
• Komplexitetsteori