Изменения
→Доказательство
<tex>NP \subset IP[1] </tex>, <tex>BPP \subset IP[0] </tex>
==Доказательство==
Первое утверждение верно, так как определить, принадлежит ли слово языку, можно за один запрос. <tex>V</tex> посылает запрос к <tex>P</tex> и в ответ либо получает сертификат, если слово принадлежит языку. Если слово не принадлежит языку, то сертификата не существует, а значит <tex>P</tex> не может его послать. <tex>P</tex> хочет убедить <tex>V</tex> в том, что слово принадлежит языку, поэтому пришлет сертификат в случае его существования.
Второе утверждение очевидно, так как для проверки принадлежности слова к языку из [[Сложностный класс BPP|BPP]] хватает вычислительной мощности <tex>V</tex>, и запросов к <tex>P</tex> делать не нужно.
==Замечание==
На самом деле <tex>NP \subset dIP[1] </tex>, где <tex> dIP[1] </tex> - аналог <tex> IP[1] </tex>, за исключением того, что <tex> V</tex> из <tex> dIP[1] </tex> - детерминированная машина Тьюринга.
