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 ${\displaystyle n}$ een priemgetal?" is bijvoorbeeld een beslissingsprobleem. Een beslissingsprobleem wordt beslisbaar genoemd als er een algoritme bestaat dat het voor elke invoer oplost.