Waarom is dit belangrijk?
Met een niet-deterministisch algoritme kunnen onderzoekers moeilijke rekenvragen aanpakken, doordat één geldige oplossingsroute volstaat ook als andere routes mislukken. In de wetenschap gebruiken onderzoekers dit model om te bepalen welke problemen een computer in redelijke tijd kan oplossen. Studenten en werknemers moeten zo'n antwoord extra controleren, omdat een poging soms een fout resultaat oplevert voordat een juiste route is gevonden.
Zo werkt het in de praktijk
In de cryptografie gebruiken ontwerpers een niet-deterministisch algoritme, zodat een aanvaller de uitkomst niet vooraf kan berekenen. Getallen die alleen op toeval lijken, zijn dan niet genoeg. De hashtabel die Hans Peter Luhn bij IBM invoerde, is een vroege datastructuur die met toeval werkt.
Onderzoek naar priemtests bouwt op dit idee. Solovay en Strassen maakten een test die voor grote getallen snel blijft, en Rabin deed hetzelfde met de test van Miller. Een even snelle test zonder toeval ontbrak toen nog.
Twee werkwijzen ordenen deze algoritmen. Een Las Vegas-algoritme geeft altijd een juist antwoord en laat de rekentijd wisselen. Een Monte Carlo-algoritme stopt binnen een vaste tijd en laat een kleine kans op een fout toe.




