Problem Detail: I’m just starting my second year in computer science and one of my classes briefly touched upon deterministic vs. non-deterministic algorithms. This got me thinking – is there any use for algorithms which return deterministic output for certain inputs, but non-deterministic output for other inputs? Say, something along the lines of $$ sleftarrow ninmathbb{R} text{if }sle 5:text{ return }2times s text{else }xleftarrowtext{generateRandomNumber()};text{ return }stimes x $$ This algorithm returns the input, doubled, if the input is less than or equal to five, and otherwise returns it multiplied by a random number (assuming the RNG returns a truly random number and is itself non-deterministic). So once again, my main question: are algorithms of this nature useful in any practical application? Additionally, what would this class of algorithm be called? Semi-deterministic? Pseudo-deterministic?
Asked By : Jules
Answered By : Yuval Filmus
First of all, your terminology is at odds with computability and complexity theory. What you are asking is whether it makes sense for an algorithm to have both randomized and non-randomized components. A good example are algorithms which have to be unpredictable (say for cryptographic reasons), but for the purpose of testing have to be predictable. In this case, we substitute a pseudorandom number generator for the true (say, physical) random number generator for testing purposes. That said, the class of algorithms you are describing are just randomized algorithms. Nothing forces a randomized algorithm to use randomization, it’s just a possibility in the model, in the same way that a non-deterministic Turing machine can be deterministic, or that a real number can be rational.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/30160 Ask a Question Download Related Notes/Documents
