# Nomenclature for deterministic algorithms that might fail

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.

• Is it important that the algorithm is deterministic? – Raphael May 7 '15 at 12:53
• 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. – Pål GD May 7 '15 at 16:00
• 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. – jsrn May 7 '15 at 17:17