Связь классов IP и AM друг с другом и с другими классами языков — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 2 промежуточные версии 2 участников) | |||
Строка 1: | Строка 1: | ||
{{В разработке}} | {{В разработке}} | ||
− | + | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Опишем работу <tex>Verifier \ V</tex> и <tex>Prover \ P</tex> для класса <tex>\mathrm{IP}</tex>. <br><br> | Опишем работу <tex>Verifier \ V</tex> и <tex>Prover \ P</tex> для класса <tex>\mathrm{IP}</tex>. <br><br> | ||
<tex>V:\Sigma^* \times \Sigma^* \times \Sigma^* \to \Sigma^* \cup \{accept, reject\} </tex>. <br> <tex>V</tex> принимает на вход: | <tex>V:\Sigma^* \times \Sigma^* \times \Sigma^* \to \Sigma^* \cup \{accept, reject\} </tex>. <br> <tex>V</tex> принимает на вход: |
Текущая версия на 19:07, 4 сентября 2022
Опишем работу
.
принимает на вход:
- Заданное слово.
- Некоторую рандомную строку. Для удобства мы предоставляем одну рандомную строку, вместо эквивалентной возможности делать вероятностные выборы в течении вычилений.
- Историю обмена сообщениями с .
На выход
.
принимает на вход:
- Заданное слово.
- Историю обмена сообщениями с .
На выход
Определим взаимодействие между и .
Для заданного слова и рандомной строки будем писать , если существует такая последовательность сообщений для некоторого , что:
- , — четное: ;
- , — четное: ;
- Последнее сообщение
Определение: |
, где — заданное слово, — рандомная строка. |
Теорема: |
Доказательство: |
Рассмотрим какой-нибудь язык
Определим:
|