Теорема Голдвассера, Сипсера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 7: Строка 7:
 
==Теорема(Голдвассер, Сипсер)==
 
==Теорема(Голдвассер, Сипсер)==
 
<tex>IP[f(n)] = AM[f(n)+2]</tex>
 
<tex>IP[f(n)] = AM[f(n)+2]</tex>
 +
 +
==План доказательства==
 +
Рассмотрим множество вероятностных лент <tex>R</tex> и его подмножество <tex>S \subset R</tex> - множество лент, на которых осуществляется допуск. Если для некоторого множества <tex>S</tex> и числа <tex>k</tex> выполняется <tex>|S| > 2K</tex>, то допустим слово.

Версия 21:09, 17 мая 2010

Определение

Протокол Артура-Мерлина - интерактивный протокол доказательства, в котором [math]A[/math](prover, Arthur) видит вероятностную ленту [math]M[/math](verifier, Merlin)(т.н. public coins)

Определение

[math]AM[f(n)][/math] - класс языков, распознаваемых с помощью интерактивного протокола доказательства Артура-Мерлина, причем количество запросов [math]A[/math] к [math]M[/math] не превышает [math]f(n)[/math].

Теорема(Голдвассер, Сипсер)

[math]IP[f(n)] = AM[f(n)+2][/math]

План доказательства

Рассмотрим множество вероятностных лент [math]R[/math] и его подмножество [math]S \subset R[/math] - множество лент, на которых осуществляется допуск. Если для некоторого множества [math]S[/math] и числа [math]k[/math] выполняется [math]|S| \gt 2K[/math], то допустим слово.