Изменения

Перейти к: навигация, поиск

PCP-теорема

41 байт добавлено, 14:03, 18 марта 2013
Экспандер графы
{{Лемма
|statement=Пусть <tex>G</tex> <tex>d</tex>-регулярный граф со вторым по величине собственным числом <tex>\lambda</tex>. Пусть <tex>F \subseteq E</tex> множество ребер. Вероятность <tex>p</tex> того, что случайный путь, начинающийся со случайного ребра из <tex>F</tex> на <tex>i+1</tex> шаге попадет <tex>F</tex> ограничена <tex>\frac {|F|} {|E|} + \left({\frac {|\lambda|} d}\right)^i</tex>.
|proof=см. [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
}}
<!--
Анонимный участник

Навигация