Класс IP — различия между версиями
(→Определение) |
(→Определение) |
||
Строка 24: | Строка 24: | ||
==Определение== | ==Определение== | ||
− | '''IP''' = '''IP'''[ | + | '''IP''' = '''IP'''[poly] - класс языков, распознаваемых с помощью интерактивного протокола доказательства с полиномиальным числом запросов от <tex>V</tex> к <tex>P</tex>. |
Версия 16:46, 6 мая 2010
Определение
Интерактивный протокол доказательства - абстрактная машина, модулирующая вычисление как передачу сообщений между двумя сущностями: вероятностная машина Тьюринга, работающая за полином и проверяющая информацию от . При этом не видит вероятностную ленту . хочет допустить слово тогда и только тогда, когда оно принадлежит языку.
- prover и - verifier. В ходе данного взаимодействия и определяют, принадлежит ли данное слово языку. имеет неограниченную вычислительную мощность и пытается доказать, что принадлежит языку. -Определение
Классом IP[f(n)] (IP = interactive proof) называется множество языков, распознаваемых с помощью интерактивного протокола доказательства. При этом:
1)
, где - вероятность того, что убедит допуститить2)
3) количество обращений к
Теорема
NP ⊂ IP[1], BPP ⊂ IP[0]
Доказательство
Первое утверждение верно, так как определить, принадлежит ли слово языку, можно за один запрос.
посылает запрос к и в ответ получает сертификат, если слово принадлежит языку. Если слово не принадлежит языку, то сертификата не существует, а значит не может его послать. хочет убедить в том, что слово принадлежит языку, поэтому пришлет сертификат в случае его существования.Второе утверждение очевидно, так как для проверки принадлежности слова к языку из BPP хватает вычислительной мощности , и запросов к делать не нужно.
Замечание
На самом деле NP ⊂ dIP[1], где dIP[1] - аналог IP[1], за исключением того, что
из dIP[1] - детерминированная машина Тьюринга.Определение
IP = IP[poly] - класс языков, распознаваемых с помощью интерактивного протокола доказательства с полиномиальным числом запросов от
к .