Классы RP и coRP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Теорема об эквивалентности определений)
м (rollbackEdits.php mass rollback)
 
(не показаны 22 промежуточные версии 6 участников)
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</tex>, которая работает за полиномиальное время, и:
+
Сложностный класс <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 \notin L \Rightarrow P(m(x) = 0) = 1</tex>;
# <tex>x \in L \Rightarrow P(m(x) = 1) \geq \frac{1}{2}</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>.
 
}}
 
}}
 +
<tex>\mathrm{RP}</tex> — сложностный класс, допускающий ошибки программ на словах из <tex>L</tex>.
 +
Заметим, что константа <tex>1/2</tex> в пункте 2 определения <tex>\mathrm{RP}</tex> может быть заменена на любую другую из промежутка <tex>(0, 1)</tex>, поскольку требуемой вероятности можно добиться множественным запуском программы.
 +
 +
<tex>\mathrm{RP}</tex> можно рассматривать как вероятностный аналог класса <tex>\mathrm{NP}</tex>, предполагая, что вероятность угадать сертификат в случае его существования не менее <tex>1/2</tex>.
 +
 +
{{Определение
 +
|definition =
 +
<tex>\mathrm{coRP} = \{L \bigm| \overline L \in \mathrm{RP}\}</tex>.
 +
}}
 +
Класс <tex>\mathrm{coRP}</tex> допускает ошибки программ на словах, не принадлежащих <tex>L</tex>.
 +
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Сложностный класс <tex>\mathrm{RP_{weak}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</tex>, которая работает за полиномиальное время, и:
+
Сложностный класс <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 \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>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=
 
|definition=
Сложностный класс <tex>\mathrm{RP_{strong}}</tex> состоит из языков <tex>L</tex> таких, что существует программа <tex>m</tex>, которая работает за полиномиальное время, и:
+
Сложностный класс <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 \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>q(|x|) \geq 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>
+
|statement=<tex>\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}</tex>.
 
|proof=
 
|proof=
<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex><br/>
+
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex><br/>
Рассмотрим язык <tex>L \in \mathrm{RP_{strong}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{strong}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>. В качестве программы <tex>m_{\mathrm{RP}}</tex> можно взять программу <tex>m_{\mathrm{RP_{strong}}}</tex>, так как <tex>1 - \frac{1}{2^p} \geq \frac{1}{2} \Leftrightarrow p \geq 1</tex>. То есть программа <tex>m_{\mathrm{RP_{strong}}}</tex> удолетворяет ограничениям сложностного класса <tex>\mathrm{RP}</tex>.<br/>
+
Рассмотрим язык <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>.<br/> Логарифмируя, получаем <br/> <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>.<br/> Разложив логарифм в ряд Тейлора, получаем<br/> <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>.<br/> Отсюда <tex>k > q(|x|)ln(2)</tex>.
 +
 
 
<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex><br/>
 
<tex>\mathrm{RP} \subset \mathrm{RP_{weak}}\colon</tex><br/>
Доказательство такое же, как в предыдущем пункте.<br/>
+
Доказательство аналогично предыдущему пункту.
<tex>\mathrm{RP_{weak}} \subset \mathrm{RP}\colon</tex><br/>
+
<tex>p_{\mathrm{RP_{weak}}}(x)</tex>
Рассмотрим язык <tex>L \in \mathrm{RP_{weak}}</tex>. Этому языку соответсвует программа <tex>m_{\mathrm{RP_{weak}}}</tex>. Для доказательства утверждения необходимо написать программу <tex>m_{\mathrm{RP}}</tex>, которая будет удолетворять ограничениям сложностного класса <tex>\mathrm{RP}</tex>.
 
<tex>m_{\mathrm{RP}}(x)</tex>
 
 
     '''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
 
     '''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
         '''if''' <tex>m_{\mathrm{RP_{weak}}}(x)</tex>
+
         '''if''' <tex>p_{\mathrm{RP}}(x)</tex>  
        '''then return''' <tex>1</tex>
+
            '''return''' <tex>1</tex>
 
     '''return''' <tex>0</tex>
 
     '''return''' <tex>0</tex>
Если слово <tex>x \notin L</tex>, то <tex>m_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>0</tex>. Тогда <tex>P(m_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. Если хотя бы один вызов программы <tex>m_{\mathrm{RP_{weak}}}(x)</tex> вернёт <tex>1</tex>, то слово <tex>x \in L</tex>. Вероятность ошибки программы <tex>m_{\mathrm{RP}}</tex> равна <tex>(1-\frac{1}{q(|x|)})^k</tex>, то есть программа <tex>m_{\mathrm{RP_{weak}}}</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>.<br/>
+
Но здесь <tex>k</tex> выбирается так, чтобы выполнялось неравенство<br/> <tex>(\frac{1}{2})^k < \frac{1}{q(|x|)}</tex>.<br/>
 +
То есть <tex>k > log_2(q(|x|))</tex>.
 +
 
 
<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex><br/>
 
<tex>\mathrm{RP} \subset \mathrm{RP_{strong}}\colon</tex><br/>
Доказательство аналогично предыдущему пункту. В этом случае <tex>k</tex> необходимо выбрать таким, что должно выполняться неравенство <tex>(\frac{1}{2})^k < 1 - \frac{1}{2^{q(|x|)}} \Leftrightarrow k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>. Разложив в ряд Тейлора получаем, что <tex>-log_{2}(1-\frac{1}{2^{q(|x|)}}) = \frac{1}{ln(2)2^{q(|x|)}} = \frac{(1+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>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>. То есть<br/><tex>k > -log_{2}(1-\frac{1}{2^{q(|x|)}})</tex>.<br/>Разложив в ряд Тейлора получаем, что<br/> <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>.<br/>То есть <tex>k</tex> надо взять больше, чем <tex>\frac{1+q(|x|)}{ln(2)}</tex>.
 +
 
 +
<tex>\mathrm{RP_{strong}} \subset \mathrm{RP}\colon</tex><br/>
 +
Для доказательства утверждения необходимо написать программу <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> надо выбрать таким, чтобы выполнялось неравенство<br/><tex>(\frac{1}{2^{q(|x|)}})^k < \frac{1}{2}</tex>.<br/> Отсюда <tex>k > \frac{1}{q(|x|)}</tex>.
 
}}
 
}}
 +
 +
== Литература ==
 +
* S.Arora, B.Barak. Randomized computation. Cambridge University, January 2007. [http://www.cs.princeton.edu/theory/complexity/bppchap.pdf]
  
 
== См. также ==
 
== См. также ==
 
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
 
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Текущая версия на 19:05, 4 сентября 2022

Определения

Определение:
Сложностный класс [math]\mathrm{RP}[/math] состоит из языков [math]L[/math] таких, что существует ВМТ [math]m[/math] такая, что для любого [math]x[/math]:
  1. [math]x \notin L \Rightarrow P(m(x) = 0) = 1[/math];
  2. [math]x \in L \Rightarrow P(m(x) = 1) \geq \frac{1}{2}[/math];
  3. [math]T(m(x, r)) \le poly(|x|)[/math] для любой вероятностной ленты [math]r[/math].

[math]\mathrm{RP}[/math] — сложностный класс, допускающий ошибки программ на словах из [math]L[/math]. Заметим, что константа [math]1/2[/math] в пункте 2 определения [math]\mathrm{RP}[/math] может быть заменена на любую другую из промежутка [math](0, 1)[/math], поскольку требуемой вероятности можно добиться множественным запуском программы.

[math]\mathrm{RP}[/math] можно рассматривать как вероятностный аналог класса [math]\mathrm{NP}[/math], предполагая, что вероятность угадать сертификат в случае его существования не менее [math]1/2[/math].


Определение:
[math]\mathrm{coRP} = \{L \bigm| \overline L \in \mathrm{RP}\}[/math].

Класс [math]\mathrm{coRP}[/math] допускает ошибки программ на словах, не принадлежащих [math]L[/math].


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


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


Теорема об эквивалентности определений

Теорема:
[math]\mathrm{RP}=\mathrm{RP_{weak}}=\mathrm{RP_{strong}}[/math].
Доказательство:
[math]\triangleright[/math]

[math]\mathrm{RP_{weak}} \subset \mathrm{RP}\colon[/math]
Рассмотрим язык [math]L \in \mathrm{RP_{weak}}[/math]. Этому языку соответсвует программа [math]p_{\mathrm{RP_{weak}}}[/math]. Для доказательства утверждения необходимо написать программу [math]p_{\mathrm{RP}}[/math], которая будет удолетворять ограничениям сложностного класса [math]\mathrm{RP}[/math].

[math]p_{\mathrm{RP}}(x)[/math]
    for [math]i = 1 \ldots k[/math] // [math]k[/math] будет определено позже
        if [math]p_{\mathrm{RP_{weak}}}(x)[/math] 
            return [math]1[/math]
    return [math]0[/math]

Если слово [math]x \notin L[/math], то [math]p_{\mathrm{RP_{weak}}}(x)[/math] всегда возвращает [math]0[/math]. Тогда [math]P(p_{\mathrm{RP}}(x) = 0) = 1[/math], при [math]x \notin L[/math]. Если хотя бы один вызов программы [math]p_{\mathrm{RP_{weak}}}(x)[/math] вернёт [math]1[/math], то слово [math]x \in L[/math]. Вероятность ошибки программы [math]p_{\mathrm{RP_{weak}}}[/math] меньше, чем [math]1-\frac{1}{q(|x|)}[/math], то есть вероятность ошибки программы [math]p_{\mathrm{RP}}[/math] меньше, чем [math](1-\frac{1}{q(|x|)})^k[/math]. [math]k[/math] надо выбрать таким, что вероятность ошибки программы [math]m_{\mathrm{RP}}[/math] при [math]x \in L[/math] была меньше [math]\frac {1}{2}[/math]. Получается неравенство [math](1-\frac{1}{q(|x|)})^k \lt \frac{1}{2}[/math].
Логарифмируя, получаем
[math]k\ ln(1-\frac{1}{q(|x|)}) \lt ln(\frac{1}{2})[/math].
Разложив логарифм в ряд Тейлора, получаем
[math]k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) \lt -ln(2)[/math].
Отсюда [math]k \gt q(|x|)ln(2)[/math].

[math]\mathrm{RP} \subset \mathrm{RP_{weak}}\colon[/math]
Доказательство аналогично предыдущему пункту.

[math]p_{\mathrm{RP_{weak}}}(x)[/math]
    for [math]i = 1 \ldots k[/math] // [math]k[/math] будет определено позже
        if [math]p_{\mathrm{RP}}(x)[/math] 
            return [math]1[/math]
    return [math]0[/math]

Но здесь [math]k[/math] выбирается так, чтобы выполнялось неравенство
[math](\frac{1}{2})^k \lt \frac{1}{q(|x|)}[/math].
То есть [math]k \gt log_2(q(|x|))[/math].

[math]\mathrm{RP} \subset \mathrm{RP_{strong}}\colon[/math]
Напишем программу [math]p_{\mathrm{RP_{strong}}}[/math], удолетворяющую ограничениям сложностного класса [math]\mathrm{RP_{strong}}[/math].

[math]p_{\mathrm{RP_{strong}}}(x)[/math]
    for [math]i = 1 \ldots k[/math] // [math]k[/math] будет определено позже
        if [math]p_{\mathrm{RP}}(x)[/math] 
            return [math]1[/math]
    return [math]0[/math]

В этом случае [math]k[/math] необходимо выбрать таким, что должно выполняться неравенство [math](\frac{1}{2})^k \lt 1 - \frac{1}{2^{q(|x|)}}[/math]. То есть
[math]k \gt -log_{2}(1-\frac{1}{2^{q(|x|)}})[/math].
Разложив в ряд Тейлора получаем, что
[math]-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)} \lt \frac{1+q(|x|)}{ln(2)}[/math].
То есть [math]k[/math] надо взять больше, чем [math]\frac{1+q(|x|)}{ln(2)}[/math].

[math]\mathrm{RP_{strong}} \subset \mathrm{RP}\colon[/math]
Для доказательства утверждения необходимо написать программу [math]p_{\mathrm{RP}}[/math], которая будет удолетворять ограничениям сложностного класса [math]\mathrm{RP}[/math].

[math]p_{\mathrm{RP}}(x)[/math]
    for [math]i = 1 \ldots k[/math] // [math]k[/math] будет определено позже
        if [math]p_{\mathrm{RP_{strong}}}(x)[/math] 
            return [math]1[/math]
    return [math]0[/math]
[math]k[/math] надо выбрать таким, чтобы выполнялось неравенство
[math](\frac{1}{2^{q(|x|)}})^k \lt \frac{1}{2}[/math].
Отсюда [math]k \gt \frac{1}{q(|x|)}[/math].
[math]\triangleleft[/math]

Литература

  • S.Arora, B.Barak. Randomized computation. Cambridge University, January 2007. [1]

См. также