Mesurer la probabilité d'erreur pour un algorithme BPP potentiel

Question

Problème

Étant donné un algorithme de recherche qui peut être utilisé pour interroger un espace de dimension k, produit à partir d'un tableau d'entrée de n données, a une complexité temporelle de $ O (klog ^ 2n) $. Cet algorithme partitionne l'espace en quatre régions sélectionne ensuite trois de ces régions en raison d'une certaine condition. De là, il sélectionne au hasard l'un des trois espaces comme l'espace suivant pour vérifier la réponse. Si cet algorithme produit une valeur, c'est à 100% la bonne solution, sinon elle ne peut pas trouver la solution qui est toujours erronée car l'élément recherché est toujours là. Là-bas, la théorie est de l'exécuter plusieurs fois jusqu'à ce qu'elle produise la solution.

Question

J'ai créé cet algorithme qui doit être utilisé comme une expérience pour créer un BPP Algorithme pour un problème d'analyse des données. Mais, je ne suis pas sûr s'il est qualifié de BPP algorithme. D'après ma compréhension, ce n'est pas le cas, car il a une chance sur trois de sélectionner la partition correcte à chaque fois qu'elle partitionne dans l'espace. Cela signifie que la probabilité de sélection de la bonne solution est $ (1/3) ^ {klogn} $ Faire la probabilité de sélectionner la solution incorrecte moins la probabilité de la bonne solution.

Donc, ma question est a) Mon interprétation est-elle correcte pour mesurer la probabilité? B) cet algorithme est-il considéré comme un BPP algorithme ou une autre classe?