Beslissingsprobleem

In de complexiteitstheorie is een beslissingsprobleem een computationeel probleem dat met 'ja' of 'nee' beantwoord dient te worden, afhankelijk van de gegeven invoer. Het probleem "is het getal n een priemgetal?" is een beslissingsprobleem want het antwoord is 'ja' of 'nee' en het antwoord hangt af van de invoer, namelijk het getal n.