Теорема о непринадлежности XOR классу AC⁰

2012-05-20T10:02:04Z

89.110.16.123:

{{Лемма
|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=
<tex>\oplus \notin \mathrm{AC^0}</tex>.
|proof=
}}

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

Теорема о непринадлежности XOR классу AC⁰