2
$\begingroup$

What do you call an algorithm which is

  • Deterministic
  • When an answer is returned, it is correct
  • For some input, the algorithm returns no answer (fails, in bounded time).

Such algorithms crop up a lot in cryptographic attacks, for instance, where a cipher is deemed broken when an attack (provably or demonstrably) works "most of the time".

I'm working in a different field (coding theory) with an algorithm of the above kind. For random, uniformly distributed input, the probability that the algorithm fails seems to be so low that in practice it can be more or less ignored. However, we have no succinct characterisation of input which cause failure. Previous work on this algorithm has called it "a probabilistic algorithm" but I find this an abuse of the term, since the algorithm is deterministic, once the input is known.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Is it important that the algorithm is deterministic? $\endgroup$ – Raphael♦ May 7 '15 at 12:53
  • $\begingroup$ Do you have a demand on how often it returns correct? Otherwise, I would just call the algorithm wrong. I can make a deterministic algorithm always failing which would be such an algorithm, for every problem. Hence this concept doesn't give much information. $\endgroup$ – Pål GD May 7 '15 at 16:00
  • 1
    $\begingroup$ Saying all such algorithms are "wrong" clearly doesn't capture that some such algorithms can be right almost all the time, and are therefore interesting. Of course, without any demand on how often it works, the "definition" makes no sense; I purposefully left this part open since there could be different classes of algorithms with notions such demands. $\endgroup$ – jsrn May 7 '15 at 17:17
2
$\begingroup$

I do not have an authorative answer but two proposals.

  1. Such algorithms compute partial functions, so you could call them partial or partially correct algorithms.

  2. Working off your literature, the class of algorithms you defined is that of Las Vegas algorithms. Even though the implication is that the algorithm is randomised it certainly need not be; even though you have access to random bits you don't have to use them.

    If you want to stress determinism, you can use deterministic Las Vegas algorithm.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ "Deterministic Las Vegas" sounds like an oxomoron :-) But I see your point; any algorithm that might fail is "Las Vegas", whether it uses randomness or not. $\endgroup$ – jsrn May 7 '15 at 12:50
  • $\begingroup$ @jsrn In fact, every total and always correct algorithm fits the class, too! (Similar reasoning: you are allowed to fail, but you don't have to.) For instance, randomised Quicksort is typically considered Las Vegas. $\endgroup$ – Raphael♦ May 7 '15 at 12:52
  • $\begingroup$ I am actually now using "Partial" to describe my examples of such functions. $\endgroup$ – jsrn May 30 '16 at 9:44

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.