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.