beräkningsproblem

Beräkningsproblem är problem som kan uttryckas som en indata och en målrelation som en beräkningsprocess eller algoritm ska uppfylla. Ett beräkningsproblem kan vara av olika slag: beslutproblem där svaret är ja eller nej, funktionsproblem där målet är att beräkna en viss funktion av indata, eller optimeringsproblem där målet är att hitta bästa möjliga värde enligt någon kostnadsfunktion.

Formellt definieras ett problem ofta genom en uppsättning instanser och en beskrivning av vilka lösningar som räknas som giltiga. Lämpliga beräkningsmodeller inkluderar Turingmaskiner och datorer; enligt Church-Turing-teorin är de lika i vad som kan beräknas i praktiken.

Beräkningsproblem studeras inom beräkningsvetenskap, logik, matematik och matematisk optimering. Viktiga begrepp är beräknbarhet (om ett problem har en algoritm som avslutas för varje indata) och effektivitet (hur längden tid och minne växer med indata).

Komplexitetsteori delar problem i klasser som P (lösta i polynomtid av en deterministisk maskin) och NP. NP-fullständiga problem är de mest kända “svåra” problem som antas inte kunna lösas i polynomtid men vars lösningar kan verifieras snabbt. Exempel på NP-fullständiga beslutproblem är SAT, och graffärggningsproblem. Funktionsproblem som är betydelsefulla inkluderar beräkning av kortaste vägen (Dijkstra/Bellman-Ford). Optimeringsproblem som Travelling Salesman Problem är också centrala.

Vissa beräkningsproblem är oändligt svåra eller obestämbara. Haltingproblemet visar att det inte finns någon allmän algoritm som avgör om ett godtyckligt program avslutas. Kunskapen om beräkningsproblem hjälper till att förstå vilka problem som i praktiken är lösliga, hur bra algoritmer kan tänkas vara, och vilka teoretiska begränsningar som gäller.