4 ms·
> nondeterministic (but predictable!) Huh? How could a nondeterministic algorithm be predictable? Do you mean algorithms with a nondeterministic but overall ir
by choeger 4y ago
> nondeterministic (but predictable!)
Huh? How could a nondeterministic algorithm be predictable? Do you mean algorithms with a nondeterministic but overall irrelevant component ("pick a random element from this set")?
- deleted 4y ago[deleted]
- User23 4y agoA simple example is algorithms that compute the value of applying associative and commutative functions. For example we can sum a set of integers by nondeterministically picking and removing an element and iterating until the set is empty. Despite the large number of possible processes, the result at termination will always be the same.
- lupire 4y agoLocal nondeterminism, where random variations can be introduced but disappears later: Example: size of a set = 1 + (remove an element from the set and then compute size of reduced set, or 0 if set is empty)