Надо написать, что V хочет установить истину. Надо расставить ссылки (например, на вероятностную МТ). Надо правильным начертанием оформить не только BPP и NP, но и всех остальных (IP, AM, GNI…). Надо закрыть фигурные скобки в определениях. Можно-нельзя достичь нельзя писать внутри определения, ибо это путает; надо, наверное, просто текстом после определения (или, лучше, обоих определений). Точки в формулирвоках теорем и последнем определении. [[Участник:Kirelagin|Кирилл Елагин]] 02:01, 4 июня 2012 (GST)

Обсуждение:Интерактивные протоколы. Класс IP. Класс AM

2012-06-03T21:52:47Z

Kirelagin: Новая страница: «Надо написать, что V хочет установить истину. Надо расставить ссылки (например, на вероят...»

Интерактивные протоколы. Класс IP. Класс AM

2012-06-03T21:52:22Z

Kirelagin: /* Класс IP */

==Класс IP==

{{Определение
|definition =
Интерактивным протоколом, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (Prover и Verifier, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;
# <tex>P</tex> не ограничен в вычислительной мощности;
# <tex>V</tex> — вероятностная машина Тьюринга;
# <tex>V</tex> ограничен полиномиальным временем работы.
}}

[[Файл:IPS.png|250px|thumb|right|Рис. 1. Схема интерактивного протокола.]]

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# public coins — <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
# private coins — <tex>P</tex> не может видеть вероятностную ленту <tex>V</tex>.

{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

Язык AM (Arthur–Merlin games) отличается от IP лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
|definition =
<tex>AM[f] = \{L|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex>. 
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V(x) = 1) = 1 </tex>, то говорят, что он обладает свойством completeness (его можно достичь).
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V(x) = 1) = 0 </tex>, то говорят, что он обладает свойством soundness (его нельзя достичь).
}}

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP[0]}</tex>
|proof=
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
}}

{{Определение
|definition=
<tex>GNI</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>GNI=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>
}}

{{Теорема
|statement=<tex>GNI \in \mathrm{IP[1]}</tex>
|proof=
Будем использовать следующий алгоритм для <tex>V</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; 
# Создадим новый граф, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>; 
# Перешлём <tex>P</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; 
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; 
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; 
# Иначе повторим первые пять шагов ещё раз и перейдём к последнему шагу; 
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.

Покажем, что это удовлетворяет ограничениям на <tex>\mathrm{IP[1]}</tex>.
Во-первых, очевидно, что число раундов не превосходит двух. 
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P</tex> сможет определить какой граф был перемешан <tex>V</tex>. Таким образом, <tex>P</tex> сможет два раза подряд вернуть правильный ответ и в итоге <tex>V</tex> вернёт 1.
* <tex> \langle G, H \rangle \notin GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P</tex> не сможет определить какой граф был перемешан <tex>V</tex>. Так как <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V</tex> просто вернёт <tex>0</tex>). Вероятность того, что <tex>V</tex> примет слово <tex>x</tex>, когда оно не принадлежит языку (то есть <tex>P</tex> два раза подряд верно угадает номер графа), равна <tex>\frac{1}{4}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}

Классы RP и coRP

2012-06-03T21:23:43Z

Kirelagin:

== Определения ==
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует [[Вероятностные вычисления. Вероятностная машина Тьюринга|ВМТ]] <tex>m</tex> такая, что для любого <tex>x</tex>:
# <tex>x \notin L \Rightarrow P(m(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(m(x) = 1) \geq \frac{1}{2}</tex>;
# <tex>T(m(x, r)) \le poly(|x|)</tex> для любой вероятностной ленты <tex>r</tex>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует ВМТ <tex>m</tex> такая, что для любого <tex>x</tex>:
# <tex>x \notin L \Rightarrow P(m(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(m(x) = 1) \geq \frac{1}{q(|x|)}</tex>, где <tex>q(|x|)</tex> — некоторый полином, <tex>q(|x|) \geq 1</tex>;
# <tex>T(m(x, r)) \le poly(|x|)</tex> для любой вероятностной ленты <tex>r</tex>.
}}
{{Определение
|definition=
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует ВМТ <tex>m</tex> такая, что для любого <tex>x</tex>:
# <tex>x \notin L \Rightarrow P(m(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(m(x) = 1) \geq 1 - \frac{1}{2^{q(|x|)}}</tex>, где <tex>q(|x|)</tex> — некоторый полином;
# <tex>T(m(x, r)) \le poly(|x|)</tex> для любой вероятностной ленты <tex>r</tex>.
}}

== Теорема об эквивалентности определений ==
{{Теорема
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>.
|proof=
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex> 
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>p_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>p_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(p_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>p_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>p_{\mathrm{RP_{weak}}}</tex> меньше, чем <tex>1-\frac{1}{q(|x|)}</tex>, то есть вероятность ошибки программы <tex>p_{\mathrm{RP}}</tex> меньше, чем <tex>(1-\frac{1}{q(|x|)})^k</tex>. <tex>k</tex> надо выбрать таким, что вероятность ошибки программы <tex>m_{\mathrm{RP}}</tex> при <tex>x \in L</tex> была меньше <tex>\frac {1}{2}</tex>. Получается неравенство <tex>(1-\frac{1}{q(|x|)})^k < \frac{1}{2}</tex>. Логарифмируя, получаем <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex> 
Доказательство аналогично предыдущему пункту.
<tex>p_{\mathrm{RP_{weak}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>. 
То есть <tex>k > log_2(q(|x|))</tex>.

<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex> 
Напишем программу <tex>p_{\mathrm{RP_{strong}}}</tex>, удолетворяющую ограничениям сложностного класса <tex>\mathrm{RP_{strong}}</tex>.
<tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}}</tex>. То есть <tex>k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <tex>-log_{2}(1-\frac{1}{2^{q(|x|)}}) = \frac{2^{-q(|x|)}}{ln(2)} + o(2^{-q(|x|)}) = \frac{(1+q(|x|)+o(q(|x|)))^{ln(\frac{1}{2})}}{ln(2)} < \frac{1+q(|x|)}{ln(2)}</tex>. То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.

<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex> 
Для доказательства утверждения необходимо написать программу <tex>p_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
<tex>p_{\mathrm{RP}}(x)</tex>
'''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
'''if''' <tex>p_{\mathrm{RP_{strong}}}(x)</tex>
'''return''' <tex>1</tex>
'''return''' <tex>0</tex>
<tex>k</tex> надо выбрать таким, чтобы выполнялось неравенство <tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>. Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Обсуждение:Сложностные классы. Вычисления с оракулом

2012-06-03T19:12:09Z

Kirelagin: /* Я не понял, ЭТО зачтено или нет? */

ЭТО КАПЕЦ [[Участник:Kirelagin|Кирилл Елагин]] 01:54, 24 апреля 2012 (GST)

Мда. Не могу не согласиться с предыдущим оратором.
Претензии по содержанию
* Мы, помнится, вводили определения не через МТ, а через программы. Напиши их именно так, пожалуйста. А если уж пишешь МТ, уточняй детерминизм оной в определении, а не в конце статьи.
* А что такое оракул?
Претензии по оформлению.
* Используй, пожалуйста, нормальные шаблоны.
* Исправь минусы на тире.
* Если объединение по чему-то, то это что-то пишется строго под знаком объединения.
* Пропущенные запятые - это так, мелочи.

== Я не понял, ЭТО зачтено или нет? ==

Если что, я остался при своём мнении, изложенном в первой строчке данного обсуждения. [[Участник:Kirelagin|Кирилл Елагин]] 22:14, 31 мая 2012 (GST)

: Действительно, стало заметно лучше ;). Но в первом определении всё ещё написан бред. «ограничение» — какое ещё ограничение? T — это просто ''время работы'' программы. С памятью аналогично. TS — вообще из другой оперы, поскольку это не число (время работы или объем памяти), а, как я понимаю из последующего использования, класс задач. И аргументы у него не программа и слово, а две функции. Ну и так дальше в том же духе… [[Участник:Kirelagin|Кирилл Елагин]] 22:51, 2 июня 2012 (GST)
: И вообще в TS надо еще написать пояснение про space-time tradeoff. [[Участник:Kirelagin|Кирилл Елагин]] 22:53, 2 июня 2012 (GST)
:: Нина зачем-то проигнорировала примерно половину комментария. Я, наверное, слишком длинно написал… [[Участник:Kirelagin|Кирилл Елагин]] 13:46, 3 июня 2012 (GST)
:::Кирилл, где ты взял space-time tradeoff? Я у Станка этого совсем не помню...
:::: Я зато помню. Это было пояснение, почему TS(f,g) != DTIME(f) ∩ DSPACE(g). Собственно, надо нормально написать определение TS (желательно, наверное, с большой фигурной скобочкой), причем ''после'' DTIME и DSPACE. А потом нужно пояснить, почему, собственно, не равно пересечению. Если не помнишь, почему, спроси у Никиты — он точно помнит, поскольку больше всех возмущался по этому поводу. [[Участник:Kirelagin|Кирилл Елагин]] 23:12, 3 июня 2012 (GST)

Обсуждение:Теорема Бейкера — Гилла — Соловэя

2012-06-03T19:08:12Z

Kirelagin: /* Мелкие по сравнению с остальным претензии */ Новая тема

Во-первых, тебе не повезло: я думал, какой бы конспект почитать, ткнул наугад и попал в твой. Во-вторых, верни, пожалуйста, на место все знаки препинания особенно точки в концах предложений и что-нибудь в районе списков). В-третьих, использовать википедийные подзаголовки где-то внутри доказательства — плохая идея (и я, честно говоря, совсем не понимаю, что с этим делать). В-четвёртых, TQBF не PS-полная, а PS-полный. А теперь я буду читать статью. [[Участник:Kirelagin|Кирилл Елагин]] 00:55, 24 апреля 2012 (GST)

Прочитай, пожалуйста, весь конспект ещё раз, исправь все проблемы согласования и лишние значки типа скобочек. Ставить тире внутри теха — идиотская идея (не только потому что такие тире отвратительно выглядят), а заодно, исправляя это, замени (как минимум) в одном месте тире на дефис. Было бы здорово, если бы ты придумал, как это доказательство записать по-нормальному, чтобы было понятно и можно было спокойно прочитать, потому что иначе это придётся делать мне и я буду не очень доволен. Особенно жутко, конечно, выглядит переход с 0-го на i-й шаг, где сразу же на ровном сыпятся какие-то утверждения про текущее состояние — надо, вероятно, поподробнее инвариант описать. [[Участник:Kirelagin|Кирилл Елагин]] 01:05, 24 апреля 2012 (GST)

: Ну в основном все поправил. Вторая часть доказательства вообще не самая ясная в целом. Там как такого инварианта нет, а мы строим множество с выполнением этого некоторого инварианта. По-моему, я это более-менее ясно написал в конспекте
:: [http://ru.wikipedia.org/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D1%8B_%D0%BE%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B9 Научись пользоваться страницами обсуждений]. И вообще довольно грустно, что ты забил на моё предложение перечитать конспект ещё раз. Да мне даже одно тире из теха пришлось самому вытащить! [[Участник:Kirelagin|Кирилл Елагин]] 00:19, 30 апреля 2012 (GST)

== Первая часть доказательства ==

Во втором утверждении, формально, написана неправда. Надо написать то же самое, но корректно.

== Вторая часть доказательства ==

В описании i-го шага прям черным по белому написано «конечное множество слов», но, блин, это вообще ниоткуа не следует (на момент прочтения) — это я и имел в виду, когда говорил про инварианты.

После описания i-го шага начинается полный трэш и с точки зрения орфографии, и с согласованием. И со смыслом тоже какая-то беда.

== Последствия ==

Из этой теоремы делаются очень глубокие и важные выводы. Про них тоже обязательно надо написать.
: «который использует операции релятивизации» — чё это за бредятина? [[Участник:Kirelagin|Кирилл Елагин]] 18:40, 7 мая 2012 (GST)

== Странное ограничение ==

Я правильно понимаю, что на <tex>i</tex>-ом шаге <tex>n</tex> не зависит от <tex>M_i</tex>? Тогда я не понимаю: что плохого в том, что машина <tex>M_i</tex> не разрешает слово <tex>1^n</tex> за <tex>2^{n - 1}</tex> шагов, потому как временной полином для этой машины вполне может выглядеть как:
<tex>p(k) = 2^n k </tex>. 
(Друзья, давайте, всё-таки, будем подписываться! Или, хотя бы, логиниться. -- [[Участник:Kirelagin|Кирилл Елагин]] 23:06, 3 июня 2012 (GST))

Я понимаю, что такое время работы программы на данном входе. Я не понимаю, что такое «программа (не) разрешает такой-то язык за время <tex>2^{n-1}</tex>». [[Участник:Kirelagin|Кирилл Елагин]] 23:06, 3 июня 2012 (GST)

== Мелкие по сравнению с остальным претензии ==

У тебя B написано то курсивным то прямым шрифтом (подсказка: посмотри в степени) (подсказка2: должно быть везде курсивным). [[Участник:Kirelagin|Кирилл Елагин]] 23:08, 3 июня 2012 (GST)

Первое следствие надо удалить, потому что оно есть во втором. Второе следствие надо переписать по-человечески. [[Участник:Kirelagin|Кирилл Елагин]] 23:08, 3 июня 2012 (GST)

2012-06-03T11:54:15Z

Kirelagin: