Beslissingsprobleem

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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.

Een beslissingsprobleem is beslisbaar als er een algoritme bestaat waarmee het probleem opgelost kan worden. Dit algoritme hoeft niet efficiënt te zijn; het bestaan ervan is voldoende om het probleem beslisbaar te laten zijn. Als er geen algoritme bestaat, spreken we over een onbeslisbaar probleem. Het stopprobleem is een bekend onbeslisbaar probleem.

Een beslissingprobleem wordt gedefinieerd als het geven van een 'ja' of 'nee' antwoord op basis van bepaalde invoer. Hierdoor kan men een beslissingsprobleem ook definiëren als de verzameling van invoerwaarden waarvoor het antwoord 'ja' is. Het beslissingsprobleem "is het getal n een priemgetal?" kan gedefinieerd worden als de oneindige verzameling { 2, 3, 5, 7, 11, ... }; dit zijn de getallen n waarvoor het antwoord 'ja' is op de gestelde vraag.