Викиконспекты - Вклад участника [ru]

Соотношение вероятностных классов

2018-06-01T15:03:30Z

188.170.72.217:

{{Теорема
|statement = <tex>\mathrm{P} \subset \mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.
|proof =
Утверждение <tex>\mathrm{P} \subset \mathrm{ZPP}</tex> является очевидным, так как программы, удовлетворяющие ограничениям <tex>\mathrm{P}</tex>, также удовлетворяют ограничениям класса <tex>\mathrm{ZPP}</tex>.

Докажем, что <tex>\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.
Для этого, покажем, что <tex>\mathrm{ZPP}_1 = \mathrm{RP} \cap \mathrm{coRP}</tex>. Тогда из <tex>\mathrm{ZPP} = \mathrm{ZPP}_1</tex> будет следовать требуемое.

1) <tex>\mathrm{ZPP}_1 \subset \mathrm{RP}</tex>. Достаточно вместо <tex>?</tex> возвращать <tex>0</tex>.

2) <tex>\mathrm{ZPP}_1 \subset\mathrm{coRP}</tex>. Достаточно вместо <tex>?</tex> возвращать <tex>1</tex>.

3) <tex>\mathrm{ZPP}_1 \supset \mathrm{RP} \cap \mathrm{coRP}</tex>.
Пусть программа <tex>p_1</tex> удовлетворяет ограничениям <tex>\mathrm{RP}</tex> и ошибается на словах из языка <tex>L</tex> с вероятностью не более <tex>1/2</tex>, а программа <tex>p_2</tex> удовлетворяет ограничениям <tex>\mathrm{coRP}</tex> и ошибается на словах не из языка <tex>L</tex> с аналогичной вероятностью. Построим программу <tex>q</tex> для <tex>\mathrm{ZPP}_1</tex>:
<tex>q</tex>(x)
'''if''' <tex>p_2</tex>(x) = 0
'''return''' 0
'''if''' <tex>p_1</tex>(x) = 1
'''return''' 1
'''return''' ?

Вероятность вывести <tex>?</tex> есть <tex>\operatorname{P}(p_2(x) = 1, p_1(x) = 0) \le 1/2</tex>.
}}

{{Теорема
|statement = <tex>\mathrm{RP} \subset \mathrm{NP} \subset \mathrm{PP} \subset \mathrm{PS}</tex>.
|proof =
1. <tex>\mathrm{RP} \subset \mathrm{NP}</tex>. Если в программе для <tex>L \in \mathrm{RP}</tex> заменить все вызовы ''random''() на недетерминированный выбор, то получим программу для <tex>L</tex> с ограничениями <tex>\mathrm{NP}</tex>.

2. <tex>\mathrm{NP} \subset \mathrm{PP}</tex>. Приведем программу <tex>q</tex> с ограничениями класса <tex>\mathrm{PP}</tex>, которая разрешает <tex>L \in \mathrm{NP}</tex>. Пусть функция ''infair_coin''() моделирует нечестную монету, а именно возвращает единицу с вероятностью <tex>1/2 - \varepsilon</tex>, где <tex>\varepsilon</tex> мы определим позже, и ноль с вероятностью <tex>1/2 + \varepsilon</tex>. Пусть также <tex>V</tex> — верификатор сертификатов для <tex>L</tex>. Тогда <tex>q</tex> будет выглядеть следующим образом:
<tex>q</tex>(x)
c <- случайный сертификат
'''if''' <tex>V</tex>(x, c)
'''return''' 1
'''return''' infair_coin()
Необходимо удовлетворить условию <tex>\operatorname{P}(q(x) = [x \in L]) > 1/2</tex>.

Пусть <tex>x \notin L</tex>. В этом случае <tex>V(x, c)</tex> вернет <tex>0</tex> и результат работы программы будет зависеть от нечестной монеты. Она вернет <tex>0</tex> с вероятностью <tex>1/2 + \varepsilon > 1/2</tex>.

Пусть <tex>x \in L</tex>. Тогда [[Формула полной вероятности|по формуле полной вероятности]] <tex>\operatorname{P}(q(x) = 1) = p_0 + (1 - p_0) (1/2 - \varepsilon)</tex>, где <tex>p_0</tex> — вероятность угадать правильный сертификат. Заметим, что поскольку длина всех сертификатов ограничена некоторым полиномом <tex>s(n), n = |x|</tex> и существует хотя бы один правильный сертификат, <tex>p_0 \ge 2^{-s(n)}</tex>. Найдем <tex>\varepsilon</tex> из неравенства <tex>\operatorname{P}(q(x) = 1) > 1/2</tex>:

<tex>p_0 + 1/2 - \varepsilon - p_0 / 2 + p_0 \varepsilon > 1/2</tex>;

<tex>p_0 / 2 + (p_0 - 1)\varepsilon > 0</tex>;

<tex>\varepsilon < \frac{p_0}{2 (1 - p_0)}</tex>.

Достаточно взять <tex>\varepsilon \le p_0 / 2</tex>. Из сделанного выше замечания следует, что работу функции ''infair_coin''() можно смоделировать с помощью не более чем <tex>s(n) + 1</tex> вызовов ''random''(). Также учтем, что длина сертификата и время работы <tex>V</tex> полиномиальны относительно <tex>|x|</tex>. Таким образом, мы построили программу <tex>q</tex>, удовлетворяющую ограничениям класса <tex>\mathrm{PP}</tex>.

3. <tex>\mathrm{PP} \subset \mathrm{PS}</tex>. Пусть <tex>p</tex> — программа для языка <tex>L \in \mathrm{PP}</tex>. Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для <tex>\mathrm{PS}</tex> будет перебирать все возможные вероятностные ленты нужной полиномиальной длины и запускать на них <tex>p</tex>. Ответом будет <tex>0</tex> или <tex>1</tex> в зависимости от того, каких ответов <tex>p</tex> оказалось больше.
}}

{{Теорема
|statement =
<tex>\mathrm{RP} \cup \mathrm{coRP} \subset \mathrm{BPP}</tex>.
|proof =
Пусть <tex>p</tex> — программа для <tex>L \in \mathrm{RP}</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом:
<tex>q</tex>(x)
u <- <tex>p</tex>(x)
v <- <tex>p</tex>(x)
'''return''' u '''or''' v
Пусть <tex>x \in L</tex>. В этом случае вероятность ошибки равна <tex>\operatorname{P}(u = 0, v = 0) = \operatorname{P}(u = 0) \cdot \operatorname{P}(v = 0) \le 1/4</tex>.

Пусть <tex>x \notin L</tex>. Тогда с вероятностью <tex>1</tex> будет верно <tex>u = 0, v = 0</tex> и <tex>q</tex> вернет правильный ответ.

Аналогично доказывается, что <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.
}}

== Литература ==
* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]

Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи

2018-06-01T14:54:19Z

188.170.72.217:

== Определения ==
{{Определение
|definition =
'''Язык <tex>L_1</tex> сводится по Карпу к языку <tex>L_2</tex> (<tex>L_1 \leq L_2</tex>)''', если существует такая функция <tex>f</tex>, работающая за полином, что <tex>x</tex> принадлежит <tex>L_1</tex> тогда и только тогда, когда <tex>f(x)</tex> принадлежит <tex>L_2</tex>.
}}

== Простой пример сведения по Карпу ==
Зададим следующие языки:
* <tex>IND</tex> — множество пар вида <tex> \langle G, k \rangle </tex>, где <tex>G</tex> — граф, а <tex>k</tex> — число, такое, что в <tex>G</tex> есть [http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%BE%D0%BC_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B5#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F независимое множество] размера <tex>k</tex>.
* <tex>CLIQUE</tex> — множество пар вида <tex> \langle G, k \rangle </tex>, где <tex>G</tex> — граф, а <tex>k</tex> — число, такое, что в <tex>G</tex> есть [http://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B8%D0%BA%D0%B0_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2) клика] размера <tex>k</tex>.
{{Теорема
|statement= <tex>IND \leq CLIQUE</tex>
|proof=
Рассмотрим функцию <tex>f( \langle G, k \rangle ) = \langle \overline{G}, k \rangle</tex>, где <tex>\overline{G}</tex> — [http://ru.wikipedia.org/wiki/%D0%94%D0%BE%D0%BF%D0%BE%D0%BB%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B3%D1%80%D0%B0%D1%84%D0%B0 дополнение графа] <tex>G</tex>. <tex>f</tex> вычислима за линейное время от длины входа, если граф задан в виде матрицы смежности. 
* (<tex>x \in L_1 \Rightarrow f(x) \in L_2</tex>). Заметим, что, если в <tex>G</tex> было независимое множество размера <tex>k</tex>, то в <tex>\overline{G}</tex> будет клика такого же размера (вершины, которые были в независимом множестве, в <tex>\overline{G}</tex> попарно соединены рёбрами и образуют клику).
* (<tex>x \in L_1 \Leftarrow f(x) \in L_2</tex>). Обратно, если в <tex>\overline{G}</tex> есть клика размера <tex>k</tex>, то в исходном графе было независимое множество размера <tex>k</tex>.
Таким образом, <tex>IND \leq CLIQUE</tex> по определению.
}}
'''Замечание.''' Другие примеры сведения по Карпу приведены в статье, содержащей [[Примеры NP-полных языков. Теорема Кука | примеры NP-полных языков]].

== Свойства сведения ==

{{Теорема
|about=о транзитивности
|statement=Сведение по Карпу транзитивно, то есть: <tex> ( L_1 \leq L_2, L_2 \leq L_3 ) \Rightarrow L_1 \leq L_3 </tex>.
|proof=
Пусть <tex>f</tex> и <tex>g</tex> — функции из определения сведения для <tex> L_1 \leq L_2 </tex> и <tex> L_2 \leq L_3 </tex> соответственно. Из определения следует: <tex>x \in L_1 \Leftrightarrow f(x) \in L_2 \Leftrightarrow g(f(x)) \in L_3</tex>.

Проверим, что <tex>g(f(x))</tex> вычислима за полиномиальное от <tex>|x|</tex> время. 
Действительно, первым делом необходимо вычислить <tex>f(x)</tex>, на это уйдет полином от <tex>|x|</tex> времени. 
Кроме того, длина входа <tex>g</tex>, являющегося выводом <tex>f(x)</tex>, тоже полиномиальна, так как за единицу времени может быть выведено не более, чем константное число символов. Значит, вычисление <tex>g(f(x))</tex> также займет времени не более, чем полином от <tex>|x|</tex>.

Таким образом, полное время работы программы есть сумма полиномов от <tex>|x|</tex> и потому тоже является полиномом от <tex>|x|</tex>.
}}

== Определения трудных и полных задач ==

{{Определение
|definition =
<tex>C</tex> — сложностный класс. Язык <tex>L</tex> называется '''<tex>C</tex>-трудным (относительно полиномиального сведения) (<tex>C</tex>-hard)''', если любой язык <tex>M</tex> из <tex>C</tex> сводится по Карпу к <tex>L</tex>: 
<tex> (L </tex> — <tex>C</tex>-hard <tex>) \overset{\underset{\mathrm{def}}{}}{\Leftrightarrow} ( \forall M \in C \Rightarrow M \leq L) </tex>.
}}

{{Определение
|definition =
<tex>C</tex> — сложностный класс. Язык <tex>L</tex> называется '''<tex>C</tex>-полным (относительно полиномиального сведения) (<tex>C</tex>-complete)''', если <tex>L</tex> является <tex>C</tex>-трудным и сам лежит в <tex>C</tex>.
}}

== Обобщение на другие ограничения на сведения ==
{{Определение
|definition =
<tex>D</tex> — класс языков, распознаваемых программами с некоторыми ограничениями. Тогда обозначим <tex>\widetilde{D}</tex> класс вычислимых функций, вычисляемых программами с теми же ограничениями.
}}
{{Определение
|definition =
'''Язык <tex>L_1</tex> <tex>\widetilde{D}</tex>-сводится по Карпу к языку <tex>L_2</tex> (<tex>L_1 \leq_{\widetilde{D}} L_2</tex>)''', если существует такая функция <tex>f</tex> из <tex>\widetilde{D}</tex>, что <tex>x</tex> принадлежит <tex>L_1</tex> тогда и только тогда, когда <tex>f(x)</tex> принадлежит <tex>L_2</tex>: 
<tex> (L_1 \leq_{\widetilde{D}} L_2) \overset{\underset{\mathrm{def}}{}}{\iff} ( \exists f \in \widetilde{D} : x \in L_1 \Leftrightarrow f(x) \in L_2 ) </tex>.
}}
'''Замечание.''' Часто используется сведение из <tex>\widetilde{P}</tex>, поэтому вместо «<tex>\widetilde{P}</tex>-сводится по Карпу» говорят просто «сводится». Также индекс у символа сведения обычно опускают.

{{Лемма
|statement=<tex>(L_1 \leq_{\widetilde{D}} L_2) \Leftrightarrow (\overline {L_1} \leq_{\widetilde{D}} \overline {L_2})</tex>
|id=lemma
|proof=
По определению сведения существует такая функция <tex>f</tex> из класса <tex>\widetilde{D}</tex>, что <tex>x \in L_1 \Leftrightarrow f(x) \in L_2</tex>. Для того, чтобы свести <tex>\overline{L_1}</tex> к <tex>\overline{L_2}</tex> будем использовать ту же функцию <tex>f</tex>. 
В самом деле: <tex>( x \in L_1 \Leftrightarrow f(x) \in L_2 ) \iff ( \overline{x \in L_1} \Leftrightarrow \overline{f(x) \in L_2} ) </tex> <tex>\iff ( x \in \overline{L_1} \Leftrightarrow f(x) \in \overline{L_2} ) \iff (\overline {L_1} \leq_{\widetilde{D}} \overline {L_2})</tex>.
}}

{{Определение
|definition =
<tex>C</tex> — сложностный класс, <tex>\widetilde{D}</tex> — класс вычислимых функций. Язык <tex>L</tex> называется '''<tex>C</tex>-трудным относительно <tex>\widetilde{D}</tex>-сведения (<tex>C</tex>-hard)''', если любой язык <tex>M</tex> из <tex>C</tex> <tex>\widetilde{D}</tex>-сводится к <tex>L</tex>: 
<tex> (L </tex> — <tex>C</tex>-hard <tex>) \overset{\underset{\mathrm{def}}{}}{\Leftrightarrow} ( \forall M \in C \Rightarrow M \leq_{f} L, f \in \widetilde{D} ) </tex>.
}}

{{Определение
|definition =
<tex>C</tex> — сложностный класс, <tex>\widetilde{D}</tex> — класс вычислимых функций. Язык <tex>L</tex> называется '''<tex>C</tex>-полным относительно <tex>\widetilde{D}</tex>-сведения (<tex>C</tex>-complete)''', если <tex>L</tex> является <tex>C</tex>-трудным относительно <tex>\widetilde{D}</tex>-сведения и сам лежит в <tex>C</tex>.
}}

[[Категория: Теория сложности]]