Лекция 4. Вероятностные вычисления

На этой Лекции мы кратко обсудили роль вероятности в вычислениях. Вероятность возникает, когда мы не знаем какой-то информации о системе. Простейшей вероятностной системой является равномерно случайный бит. Используя детерминированные операции и набор независимых случайных битов, можно реализовать произвольные вероятностные операции. Энтропия Шеннона $H(p)$ заданного распределения вероятности $p$ является мерой того, насколько смешанное состояние случайно. У этой величины есть операциональный смысл: $m$ копий распределения $p$ можно реализовать детерминированными преобразованиями при помощи $\approx m H(p)$ случайных бит; и наоборот, $m$ копий распределения $p$ сжимаются до $\approx m H(p)$ случайных бит. Мы считаем, что задача эффективно решается на вероятностных схемах, если существует равномерное семейство вероятностных схем, разрешающее язык с высокой вероятностью.