"машина на вході дає відповідь" так "при зазначеної в послідовності результатів підкидань монети ". Цей предикат з очевидних причин задовольняє визначенню 3.2.
Опр. 3.2 опр. 3.1. Випадково вибираємо слово довжини і підставляємо в предикат, потім обчислюємо значення предиката. Така ВМТ задовольняє визначенню 3.1.
Визначення 3.2 допускає наступне наочне тлумачення. Зазначимо на площині точки з безлічі . Для розглянемо перетин цієї множини. Предикат , що бере участь у визначенні 3.2, володіє таким дивним властивістю, що міра цього перерізу при будь-якому або більше , або менше . Це розділяє значення на дві категорії: одна відповідає істинності предиката , інша - хибність.
В
Малюнок 3.1: Перетин безлічі
Класичний приклад завдання з BPP представляє перевірка простоти числа: дано число , потрібно визначити, просте воно. Для цього завдання існує імовірнісний алгоритм, що працює за поліноміальний час; він буде зараз описаний.
Необхідні відомості з теорії чисел.
Детальний виклад елементарної теорії чисел міститься в книзі [<# "11" src = "doc_zip740.jpg"/> - просте і, то.
Китайська теорема про залишки. Нехай - розкладання числа на взаємно прості множники. Тоді. p> Іншими словами, існує взаємно однозначна відповідність між залишками від ділення на і парами залишків від ділення на і на. {І це відповідність поважає операції додавання і множення.) p> З малої теореми Ферма випливає, що дозволяє стверджувати, що - складене (кажуть, що є свідком непростота числа). Це свідчення непряме - явного розкладання на множники ми не отримуємо - і сильне: часто досить перевірки прі! p> Однак перевірки малої теореми Ферма навіть при всіх може виявитися недостатньо. Алгоритм перевірки буде використовувати свідків ще одного типу: якщо, а, то - складене; і мають загальний дільник, більший 1. Тому свідки такого виду (взагалі кажучи, набагато більш рідко з'являються) дозволяють відразу ж вказати розкладання (проти простоти якого вони свідчать) на два множника за поліноміальний час (найбільший спільний дільник двох чисел і можна знайти за поліноміальний час, див. нижче).
Необхідні відомості з алгоритмічної теорії чисел.
Арифметичні операції над числами можна виконувати за поліноміальний час від довжини їх запису (число записується знаками). Напр...
