# What is the correct term for a probabilistically complete algorithm?

I'm wondering what the correct term for an algorithm that is probabilistically complete is. An algorithm is probabilistically complete if the probability of finding a solution, should a solution exist, approaches one as the runtime goes to infinity.

A motion planner such as PRM will eventually find a solution if one exists, but cannot show that that no motion exists. This would be similar to an algorithm that semi-decides a problem, but the "yes" output is a trajectory, so it's not really a decision problem. Is there an accepted term for such algorithms? (Something like, PRM is semi-deciding)?

• This is somewhat similar to a Las Vegas algorithm, without the asymmetry between the true and false instances. – Yuval Filmus May 17 '18 at 17:58
• Are you sure your algorithm is probabilistic? This term has a specific meaning in mathematics and computer science, which is different than its normal meaning. – Yuval Filmus May 17 '18 at 17:59
• I know the term probabilistic completeness is the standard for the field (en.wikipedia.org/wiki/Motion_planning). I'm not sure what the specific meaning you're referring to is. – Andrew W May 17 '18 at 18:16
• It seems that probabilistic completeness is indeed very similar to being a Las Vegas algorithm. I imagine that in motion planning the goal is to produce a plan, so if the term probabilistic complete is used there, it probably refers to what you are looking for. Different terms are used elsewhere. – Yuval Filmus May 17 '18 at 18:34