Problem med avgörandet
Inom beräkningsbarhetsteorin och komplexitetsteorin är ett beslutsproblem en fråga i ett formellt system med ett ja- eller nej-svar. Svaret är beroende av värdena på de ingående parametrarna. Beslutsproblem förekommer vanligtvis i matematiska frågor om avgörbarhet, dvs. frågan om det finns en effektiv metod för att avgöra om ett objekt existerar eller om det tillhör en mängd. Några av de viktigaste problemen inom matematiken är omöjliga att avgöra.
Ett beslutsproblem har endast två möjliga utgångar, ja eller nej (eller växelvis 1 eller 0) för varje inmatning.
Frågor och svar
F: Vad är ett beslutsproblem?
S: Ett beslutsproblem är en fråga i något formellt system med ett ja-eller-nej-svar, beroende på värdena på ingångsparametrarna.
F: Inom vilka områden förekommer beslutsproblem?
S: Beslutsproblem uppträder vanligtvis i matematiska frågor om decidabilitet.
F: Vad är innebörden av decidability?
S: Decidability avser frågan om det finns en effektiv metod för att fastställa existensen av ett objekt eller dess medlemskap i en uppsättning.
F: Är alla problem inom matematiken möjliga att lösa?
S: Nej, några av de viktigaste problemen inom matematiken är oavgörbara.
F: Vad är ett oavgörbart problem?
S: Ett oavgörbart problem är ett problem för vilket det inte finns någon algoritm som alltid kan ge ett ja-eller-nej-svar inom en ändlig tid.
F: Är svaret på ett beslutsproblem alltid ja eller nej?
S: Ja, svaret på ett beslutsproblem är alltid ja eller nej.
F: Vad beror svaret på ett beslutsproblem på?
S: Svaret på ett beslutsproblem beror på värdena för de ingående parametrarna.
