Beslissingsprobleem

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

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.

Definitie[bewerken | brontekst bewerken]

De invoer van een beslissingsprobleem moet een vorm hebben die in principe in eindige tijd door een algoritme kan worden ingelezen. Daarvoor kiezen we een eindige verzameling (het alfabet) en spreken af dat een invoerwaarde een eindige string over dit alfabet is. We definiëren:

Een belissingsprobleem is een functie

Vaak wordt een beslissingsprobleem gedefinieerd door de verzameling positieve invoerwaarden te geven:

Een beslissingsprobleem is een deelverzameling .

De twee definities zijn equivalent: een beslissingsprobleem volgens de eerste definitie is de indicatorfunctie van een beslissingsprobleem volgens de tweede definitie.

Als we de tweede definitie gebruiken, is een beslissingsprobleem hetzelfde als een taal in de theorie van formele talen, waardoor we de uitdrukkingskracht van formalismen als grammatica's, eindige automaten en Turingmachines met elkaar kunnen vergelijken.

Andere soorten objecten kunnen ook als invoer worden gebruikt, maar die moeten eerst als strings worden gecodeerd. In de praktijk is de specifieke codering niet belangrijk en wordt die vaak impliciet gelaten.

Beslisbaarheid[bewerken | brontekst bewerken]

Een beslissingsprobleem is beslisbaar als er een algoritme bestaat waarmee het probleem in eindige tijd 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.

Voorbeelden[bewerken | brontekst bewerken]

  • De contextvrije taal over het alfabet is een beslissingsprobleem. Deze taal bevat alle strings die uit een aantal 's gevolgd door hetzelfde aantal 's bestaan. Dit beslissingsprobleem is beslisbaar (alle contextvrije talen zijn beslisbaar).
  • Bepalen of een getal een priemgetal is is een beslissingsprobleem gegeven door . Dit beslissingsprobleem is beslisbaar, omdat we elk getal in factoren kunnen ontbinden. Merk op dat we in dit voorbeeld de codering impliciet hebben gelaten, maar getallen kunnen als eindige rijtjes worden weergegeven, bijvoorbeeld met behulp van het binaire of het decimale talstelsel.
  • Het stopprobleem wordt gedefinieerd door de verzameling . Ook hier is het impliciet gelaten hoe Turingmachines als string gecodeerd worden, maar het is bekend dat dat mogelijk is. Het stopprobleem is een voorbeeld van een niet-beslisbaar beslissingsprobleem.
  • Het vervulbaarheidsprobleem wordt gedefinieerd door de verzameling . Het vervulbaarheidsprobleem is een beslisbaar, NP-volledig beslissingsprobleem.

Literatuur[bewerken | brontekst bewerken]

  • Elaine Rich. Automata, Computability and Complexity, Theory and Applications. Pearson, 2008.
  • Uwe Schöning. Theoretische Informatik - Kurz gefasst (5. Auflage). Spektrum, 2008.

Zie ook[bewerken | brontekst bewerken]