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

Материал из Викиконспекты
Перейти к: навигация, поиск

ToDo

  1. В лемме нужно объяснить, что такое [math]f|_p[/math], что такое [math]Pr[/math] (пояснить). Перенести формулу на новую строчку.
  2. Выделить строчку после доказательства как замечание.
  3. Дописать 5-ый пункт в «не умаляя общности» (про глубину листов).
  4. Сделать что-нибудь со фразой: «На каждом шаге случайным образом будем назначать все большее число переменных.» (убрать её), и написать нормально 2 следующих фразы.
  5. Я долго осиливал фразу «Отсюда по лемме получаем, что с вероятностью…» Её надо переписать, вставив приличное количество промежуточных шагов.
  6. Добавить пояснение для фразы «При достаточно больших [math]n[/math]…».
  7. Написать, откуда берётся [math]9/10[/math].
  8. «невозможно сделать постоянной, зафиксировав менее…» переписать, убрав слова «менее [math]n[/math].