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