Теорема о непринадлежности XOR классу AC⁰
Версия от 13:02, 20 мая 2012; 89.110.16.123 (обсуждение)
| Лемма: |
Пусть представима в виде k-ДНФ, а случайная выборка случайных бит входа. Тогда при верно не представима в виде s-КНФ. |
| Теорема: |
. |
| Лемма: |
Пусть [math]f[/math] представима в виде k-ДНФ, а [math]p~-[/math] случайная выборка [math]t[/math] случайных бит входа. Тогда при [math]s \ge 2[/math] верно [math]Pr[f|_p[/math] не представима в виде s-КНФ[math]]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2}[/math]. |
| Теорема: |
[math]\oplus \notin \mathrm{AC^0}[/math]. |
