Non-determinisme

Med en non-deterministisk problemløsning menes der i datalogi en algoritme med en række valgpunkter, med den egenskab, at hvis det rigtige alternativ vælges i hvert valgpunkt, så nås mindst én løsning på problemet. I algoritmen angives, hvad der er acceptable løsninger, og hvad der ikke er. Hvorledes der vælges, specificeres ikke. Dette er en grundteknik i deklarativ programmering, fordi det giver mulighed for at angive valgmuligheder i problembeskrivelsen uden at skulle tage stilling til præcist, hvorledes eller hvornår valg foretages.

Non-determininsme kan simuleres/implementeres på flere forskellige måder ved at bruge forskellige søgestrategier og metaræsonnement (se dybde-først-søgning, logikprogrammering og PROLOG). Som resultat fås i teorien garanti for, at alle løsninger på problemet findes. Denne garanti kan overføres til praksis, såfremt implementationen er korrekt.