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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема об эквивалентности определений)
(Теорема об эквивалентности определений)
Строка 31: Строка 31:
 
     <tex>f = 0</tex> // столько раз программа <tex>m_{\mathrm{RP_{weak}}}</tex> вернула <tex>false</tex>
 
     <tex>f = 0</tex> // столько раз программа <tex>m_{\mathrm{RP_{weak}}}</tex> вернула <tex>false</tex>
 
     <tex>t = 0</tex> // столько раз программа <tex>m_{\mathrm{RP_{weak}}}</tex> вернула <tex>true</tex>
 
     <tex>t = 0</tex> // столько раз программа <tex>m_{\mathrm{RP_{weak}}}</tex> вернула <tex>true</tex>
     '''for''' <tex>i = 1 \ldots k</tex>
+
     '''for''' <tex>i = 1 \ldots k</tex> // <tex>k</tex> будет определено позже
 
         '''if''' <tex>m_{\mathrm{RP_{weak}}}(x)</tex>
 
         '''if''' <tex>m_{\mathrm{RP_{weak}}}(x)</tex>
 
         '''then''' <tex>f = f + 1</tex>
 
         '''then''' <tex>f = f + 1</tex>
 
         '''else''' <tex>t = t + 1</tex>
 
         '''else''' <tex>t = t + 1</tex>
 
     '''return''' <tex>f > t \ ? \ false : true</tex>
 
     '''return''' <tex>f > t \ ? \ false : true</tex>
Если слово <tex>x \notin L</tex>, то <tex>m_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>false</tex>. Тогда <tex>P(m_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. <tex>k</tex> надо выбрать таким, что вероятность ошибки программы <tex>m_{\mathrm{RP}}(x)</tex> при <tex>x \in L</tex> была меньше <tex>\frac {1}{2}</tex>. Вероятность ошибки программы равна <tex>(1-\frac{1}{q(|x|)})^k</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>x \notin L</tex>, то <tex>m_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>false</tex>. Тогда <tex>P(m_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</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</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>\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 < \frac{1}{q(|x|)}</tex>. Прологарифмировав и сократив на <tex>ln(\frac{1}{2})</tex>, получаем, что <tex>k > q(|x|)</tex>.
 
}}
 
}}
  
 
== См. также ==
 
== См. также ==
 
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
 
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

Версия 20:18, 23 мая 2012

Определения

Определение:
Сложностный класс [math]\mathrm{RP}[/math] состоит из языков [math]L[/math] таких, что существует программа [math]m[/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].


Определение:
Сложностный класс [math]\mathrm{RP_{weak}}[/math] состоит из языков [math]L[/math] таких, что существует программа [math]m[/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].


Определение:
Сложностный класс [math]\mathrm{RP_{strong}}[/math] состоит из языков [math]L[/math] таких, что существует программа [math]m[/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] — некоторый полином, [math]q(|x|) \geq 1[/math].

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

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

[math]\mathrm{RP_{strong}} \subset \mathrm{RP}\colon[/math]
Рассмотрим язык [math]L \in \mathrm{RP_{strong}}[/math]. Этому языку соответсвует программа [math]m_{\mathrm{RP_{strong}}}[/math]. Для доказательства утверждения необходимо написать программу [math]m_{\mathrm{RP}}[/math], которая будет удолетворять ограничениям сложностного класса [math]\mathrm{RP}[/math]. В качестве программы [math]m_{\mathrm{RP}}[/math] можно взять программу [math]m_{\mathrm{RP_{strong}}}[/math], так как [math]1 - \frac{1}{2^p} \geq \frac{1}{2} \Leftrightarrow p \geq 1[/math]. То есть программа [math]m_{\mathrm{RP_{strong}}}[/math] удолетворяет ограничениям сложностного класса [math]\mathrm{RP}[/math].
[math]\mathrm{RP} \subset \mathrm{RP_{weak}}\colon[/math]
Доказательство такое же, как в предыдущем пункте.
[math]\mathrm{RP_{weak}} \subset \mathrm{RP}\colon[/math]
Рассмотрим язык [math]L \in \mathrm{RP_{weak}}[/math]. Этому языку соответсвует программа [math]m_{\mathrm{RP_{weak}}}[/math]. Для доказательства утверждения необходимо написать программу [math]m_{\mathrm{RP}}[/math], которая будет удолетворять ограничениям сложностного класса [math]\mathrm{RP}[/math].

[math]m_{\mathrm{RP}}(x)[/math]
    [math]f = 0[/math] // столько раз программа [math]m_{\mathrm{RP_{weak}}}[/math] вернула [math]false[/math]
    [math]t = 0[/math] // столько раз программа [math]m_{\mathrm{RP_{weak}}}[/math] вернула [math]true[/math]
    for [math]i = 1 \ldots k[/math] // [math]k[/math] будет определено позже
        if [math]m_{\mathrm{RP_{weak}}}(x)[/math]
        then [math]f = f + 1[/math]
        else [math]t = t + 1[/math]
    return [math]f \gt  t \ ? \ false : true[/math]

Если слово [math]x \notin L[/math], то [math]m_{\mathrm{RP_{weak}}}(x)[/math] всегда возвращает [math]false[/math]. Тогда [math]P(m_{\mathrm{RP}}(x) = 0) = 1[/math], при [math]x \notin L[/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[/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_{strong}}\colon[/math]

Доказательство аналогично предыдущему пункту. В этом случае [math]k[/math] необходимо выбрать таким, что должно выполняться неравенство [math](\frac{1}{2})^k \lt \frac{1}{q(|x|)}[/math]. Прологарифмировав и сократив на [math]ln(\frac{1}{2})[/math], получаем, что [math]k \gt q(|x|)[/math].
[math]\triangleleft[/math]

См. также