In the Vinony graph
Within Vinony's link graph, класс ZPP is referenced by 90 other articles, and connects out to BPP, expectation and quantum computing.
It is catalogued under the topic Probabilistic complexity classes.
Its subject is documented across 13 Wikipedia language editions.
Article · Русский
В теории вычислительной сложности ZPP (англ. zero-error probabilistic polynomial time — безошибочный вероятностный полиномиальный) — это класс задач с ответом «Да» либо «Нет», для которых существует вероятностная машина Тьюринга, удовлетворяющая следующим свойствам: * Она всегда правильно отвечает «Да» либо «Нет». * Математическое ожидание времени работы данной машины Тьюринга полиномиально (само время работы может быть неограниченно велико). Существует альтернативный набор свойств: * Машина Тьюринга всегда работает за полиномиальное время. * Она отвечает «Да», «Нет» или «Не знаю». * Ответ может быть либо правильным, либо «Не знаю». * Если правильный ответ «Да», машина Тьюринга отвечает «Да» с вероятностью не меньше ½. * Если правильный ответ «Нет», машина Тьюринга отвечает «Нет» с вероятностью не меньше ½. Выбор одного из двух наборов свойств приводит к эквивалентным определениям класса ZPP. Машину Тьюринга, удовлетворяющую этим свойствам, иногда называют машиной Тьюринга типа Лас-Вегас.
Abstract from DBpedia / Wikipedia · CC BY-SA