2
$\begingroup$

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

$$ s\leftarrow n\in\mathbb{R}\\ \text{if }s\le 5:\text{ return }2\times s\\ \text{else }x\leftarrow\text{generateRandomNumber()};\text{ return }s\times 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?

$\endgroup$
  • 3
    $\begingroup$ Are you really sure that random numbers have something to do with non-determinism? Check again. $\endgroup$ – babou Sep 20 '14 at 17:09
  • 2
    $\begingroup$ What @babou said. Also, an algorithm that is non-deterministic/randomized for some inputs is, by definition, non-deterministic/randomized. $\endgroup$ – Raphael Sep 20 '14 at 17:32
  • 3
    $\begingroup$ non-deterministic does not mean has-multiple-possible-answers $\endgroup$ – Eben Sep 21 '14 at 0:42
5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Such algorithms certainly exist and are of practical nature. Algorithms that are deterministic for some input instances and non-deterministic for others are still simply called non-deterministic. When I say "practical nature", it should be added that true non-determinism still does not exist in computers. Yet, the study of non-deterministic branching makes sense anyway as it is helpful computational model.

Note that many non-deterministic algorithms for inputs of arbitrary length will work in a deterministic manner on an empty input string. So that is one rather trivial example.

But coming to a more practical example, consider modern SAT (satisfiability) solving. Here, decisions are made seemingly non-deterministic (in reality, there are advanced heuristics to make these) and back-tracked whenever needed (so that a non-deterministic reasoning scheme is still complete on a deterministic computer). To make reasoning more efficient, so-called clause learning and unit propagation are applied, which reduce the number of decisions that the algorithm has to make. There are more simple input instances for which no non-deterministic decision ever has to be made, as unit propagation alone solves the instance already.

The SAT solving case may not be convincing to everyone as I am arguing that essentially, a non-deterministic search algorithm with unit propagation is executed on a deterministic machine by performing decision making and back-tracking. But since you are asking for practical applications of a non-deterministic algorithm (and we do not have "guessing computers"), I think that this is a fair answer. It should be added that the "clause learning" applied nowadays in SAT solving does not fit into this scheme, however.

$\endgroup$
  • $\begingroup$ "True non-determinism still does not exist in computers" What about a hashing algorithm which generates a distinct random salt for any input, and uses a true random number generator to achieve this? Wouldn't that qualify as true non-determinism? $\endgroup$ – Jules Sep 22 '14 at 15:09
  • $\begingroup$ No, because non-determinism in the context of computation models means that the answer to the question under concern is "TRUE" if and only if the system has some way to say "TRUE" for some guessed transitions. You seem to equal "Non-deterministic" with "does not behave in a precisely predictable way". These are different concepts. This definition of "non-deterministic" is also used for talking about algorithms, which is what your original question is about. $\endgroup$ – DCTLib Sep 23 '14 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.