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

Definitie

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 $\Sigma$ (het alfabet) en spreken af dat een invoerwaarde een eindige string over dit alfabet is. We definiëren:

Een belissingsprobleem is een functie $P\colon \Sigma ^{*}\to \{0,1\}$

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

Een beslissingsprobleem is een deelverzameling $P\subseteq \Sigma ^{*}$.

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

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

• De contextvrije taal $\{a^{n}b^{n}\mid n\in \mathbb {N} \}$ over het alfabet $\{a,b\}$ is een beslissingsprobleem. Deze taal bevat alle strings die uit een aantal $a$'s gevolgd door hetzelfde aantal $b$'s bestaan. Dit beslissingsprobleem is beslisbaar (alle contextvrije talen zijn beslisbaar).
• Bepalen of een getal een priemgetal is is een beslissingsprobleem gegeven door ${\textit {PRIMES}}=\{x\mid x{\text{ is een priemgetal}}\}$. 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 $\{(M,x)\mid M{\text{ is een Turingmachine die, met }}x{\text{ als invoer, in een eindig aantal stappen termineert}}\}$. 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 ${\textit {SAT}}=\{p\mid p{\text{ is een vervulbare zin in de propositielogica}}\}$. Het vervulbaarheidsprobleem is een beslisbaar, NP-volledig beslissingsprobleem.

Literatuur

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

Zie ook

• Entscheidungsproblem