Algorithmes de Monte Carlo: y a-t-il des problèmes où deux algorithmes en face de Monte Carlo pourraient le résoudre?

Question

J'ai commencé à lire sur des algorithmes probabilistes et des algorithmes Monte-Carlo. Puisqu'un Monte-Carlo ne peut donner qu'une certaine réponse pour vrai ou faux, je me demandais s'il était concevable que pour le même problème, il existe deux algorithmes opposés de Monte-Carlo capables de donner une certaine réponse. (Par opposé, je veux dire l'un serait sûr quand c'est faux, et l'autre serait certain quand c'est vrai)

Par exemple : Il existe un algorithme basé sur le test de numéro de premier nombre qui peut vérifier si un nombre "n" est ou non. Si la réponse est fausse, alors "n" n'est pas un nombre premier (c'est un nombre composé). Cependant, si la réponse devait être vraie, alors "n" pourrait être primordial (avec une certaine probabilité). À ma connaissance, il n'y a pas d'algorithme efficace (Monte-Carlo) capable de dire avec certitude si "n" est un nombre premier.