Article · Русский
В теории вычислительной сложности ZPP (англ. zero-error probabilistic polynomial time — безошибочный вероятностный полиномиальный) — это класс задач с ответом «Да» либо «Нет», для которых существует вероятностная машина Тьюринга, удовлетворяющая следующим свойствам: * Она всегда правильно отвечает «Да» либо «Нет». * Математическое ожидание времени работы данной машины Тьюринга полиномиально (само время работы может быть неограниченно велико). Существует альтернативный набор свойств: * Машина Тьюринга всегда работает за полиномиальное время. * Она отвечает «Да», «Нет» или «Не знаю». * Ответ может быть либо правильным, либо «Не знаю». * Если правильный ответ «Да», машина Тьюринга отвечает «Да» с вероятностью не меньше ½. * Если правильный ответ «Нет», машина Тьюринга отвечает «Нет» с вероятностью не меньше ½. Выбор одного из двух наборов свойств приводит к эквивалентным определениям класса ZPP. Машину Тьюринга, удовлетворяющую этим свойствам, иногда называют машиной Тьюринга типа Лас-Вегас.
Abstract from DBpedia / Wikipedia · CC BY-SA