beslissingsprobleem

In de berekenbaarheids- en complexiteitstheorie is een beslissingsprobleem een computationeel probleem dat, afhankelijk van de gegeven invoer, met 'ja' of 'nee' beantwoord dient te worden. Het probleem "is het getal een priemgetal?" is bijvoorbeeld een beslissingsprobleem. Een beslissingsprobleem wordt beslisbaar genoemd als er een algoritme bestaat dat het voor elke invoer oplost.