ќкремо зупинимось на ймов≥рн≥сних алгоритмах дл¤ задач розп≥знаванн¤. …мов≥рн≥сний (ћонте  арло) алгоритм розп≥знаЇ мову з одноб≥чною помилкою, де , ¤кщо дотриман≥ так≥ умови:

1)      ¤кщо , то приймаЇ вх≥д з ≥мов≥рн≥стю 1;

2)      ¤кщо , то в≥дхилаЇ вх≥д з ≥мов≥рн≥стю принаймн≥ .

Ќехай ймов≥рн≥сний алгоритм розп≥знаЇ мову з одноб≥чною помилкою, використовуючи на вход≥ довжини випадкову посл≥довн≥сть довжини . ¬ цьому випадку Ї ефективний спос≥б зменшенн¤ помилки. –озгл¤немо ймов≥рн≥сний алгоритм , ¤кий на вход≥ працюЇ наступним чином:

Ј         використовуЇ випадкову посл≥довн≥сть довжини , де , розбивши њњ на †частин довжини †кожна;

Ј         моделюЇ роботу алгоритму на вход≥ з використанн¤м кожноњ ≥з випадкових посл≥довностей , ≥ отримуЇ результат≥в моделюванн¤ , де

Ј         подаЇ на вих≥д 1, ¤кщо вс≥ дор≥внюють 1, ≥ 0, ¤кщо серед них Ї хоча б один 0.

ѕерев≥римо, що алгоритм розп≥знаЇ ту ж мову †≥ оц≥нимо ймов≥рн≥сть помилки. якщо , то алгоритм видаЇ 1 незалежно в≥д набору випадковоњ посл≥довност≥. “ому †дл¤ вс≥х, ≥ у цьому випадку приймаЇ з ймов≥рн≥стю 1. якщо , то з ймов≥рн≥стю щонайб≥льше , дл¤ кожного .ќск≥льки †Ї випадковими ≥ незалежними м≥ж собою, то р≥вн≥сть виконуЇтьс¤ дл¤ вс≥х з ймов≥рн≥стю не б≥льшою н≥ж . ѕриходимо до висновку, що приймаЇ не з ≥з ймов≥рн≥стю щонайб≥льше †≥, таким чином, розп≥знаЇ з одноб≥чною помилкою .

¬ажливе зауваженн¤ пол¤г¤Ї в тому, що† алгоритм пол≥ном≥альний, то таким Ї ≥ алгоритм , причому не лише дл¤ константи, а й дл¤ будь-¤кого -пол≥ному в≥д довжини входу. ѕоклавши дл¤ в≥дпов≥дноњ константи , бачимо, що ¤кщо множина розп≥знаЇтьс¤ пол≥ном≥альним ймов≥рн≥сним алгоритмом ≥з одноб≥чною помилкою , дл¤ константи м≥ж 0 ≥ 1, то ц¤ ж множина розп≥знаЇтьс¤ де¤ким пол≥ном≥альним алгоритмом ≥з одноб≥чною помилкою . …мов≥рн≥сть такого пор¤дку називають експоненц≥йно низькою. “аким чином, експоненц≥йне зниженн¤ помилки (до ) дос¤гаЇтьс¤ ц≥ною всього лише л≥н≥йного зб≥льшенн¤ часу роботи (у раз≥в).