Обсуждение:Теорема Лаутемана

ToDo

Баги:

1. Надо убрать это никому не нужное предисловие, а название поместить в графу |about теоремы (разумеется, ссылки нужно сохранить + см. п. 2).
2. Не должно быть никаких ссылок НА СТАРЫЕ КОНСПЕКТЫ.
3. Я, если честно, не вижу ссылки на доказательство того, что BPP замкнут относительно дополнения. Думаю, если ты не найдёшь этого факта в нынешней вики, его нужно сделать леммой прямо в этом конспекте.
4. «BPP можно определить как…» Продолжение этой фразы ужасно. Мы не мешаем формулы и русский язык. В данном конкретном случае, мне кажется, лучше написать на русском.
5. «k-большим, если…» откуда вообще берутся [math]g_i[/math]? Туда же: если k-большим мы называем, то почему k-маленькое у нас является? Надо использовать схожие по смыслу слова.
6. «Существует вероятностная машина Тьюринга M, такая что…» Ссылку на ВМТ.
7. Прямо дальше ты неявно воспользовался теоремой о совпадении классов BPP и BPPstrong.
8. «Если [math]x \in L[/math]…» Прямо за этим: у множества [math]A_x[/math] нет вероятности. Это множество.
9. «Потребуем [формула], чтобы [math]A_x[/math] было бы k-большим.» Это подстановка [math]|A_x [/math] ну оооочень нетривиальна. Чтобы её осознать, мне пришлось думать минут 5. Нужно это как-нибудь пояснить.
10. Нагромождение формул в предпоследней строчке невозможно понять первые раз 5.

Реквестирую:

• исправление этих багов;
• замену всех выражений типа «существует х, такой, что существует у…» на «существует такой х, что существует у», ну или доказательство того, что у тебя в конспекте в подобных конструкциях правильно стоят запятые;
• везде, где написано «[math]A_x[/math] [math]k[/math]-большое», поставить тире;
• в итоге попытаться перечитать конспект, как будто ты его раньше никогда не читал и сделать так, чтобы понятно с первого раза стало кому угодно, даже мне.

ToDo 2

1. Почему нет ссылок? На BPP, например? А, я нашёл их! Но сделай их лучше референсами. Как это делается, посмотри, например, у Иры в конспекте.
   1. Я что-то не уверен, что стоит так делать, потому что Андрей Сергеевич пишет "1) Что за дурацкая ссылка [1] вверху? Интервики так не делают." в описании про конспект "Класс P".
2. Второй пункт в первой лемме вообще ни о чём, второе следствие там необосновано. Мне кажется, что ты хотел написать там что-то дпугое, не так ли?
   1. Как ни о чём? [math]\overline{L} \in \mathrm{BPP}[/math], а выше сказано что дополнение языка из [math]\mathrm{BPP}[/math] опять из [math]\mathrm{BPP}[/math]. Значит [math]L \in \mathrm{BPP}[/math].
3. «…тогда и только тогда, когда существует «много» таких вероятностных лент…» Что там такое дальше [math]R(x,y)[/math]? Откуда оно вообще взялось?
4. «Таким образом, необходимо уметь записывать «существует много» с помощью кванторов…» Это всё-таки перечисление, а перечисление пишется через запятую.
5. «Если [math]|X| \lt \frac{2^t}{k}[/math], то [math]X[/math] является [math]k[/math]-маленьким.» Эээ… нет, X называется k-маленьким, если оно не k-большое. А это какое-то второе определение, причём эквивалентность этих определений нигде не доказана.
   1. Это не определение, а очевидный факт, что [math]k[/math] копиями множества [math]X[/math] нельзя покрыть множество [math]G[/math], а потому оно не может быть [math]k[/math]-большим, а значит, по определению, которое указано выше, является [math]k[/math]-маленьким.
6. Как ты заметил, тех здесь не поддерживает слишком длинные формулы. И разбивает он их как получится. Поэтому надо сделать так, чтобы переносы были логичными. Подсказка: надо разбить формулу на несколько в логичных местах (например, на знаке равенства).
7. «Получаем [math]\frac{r(n)}{p(n)} \lt k \lt 2^{p(n)}[/math], то есть [math]x \in L \Leftrightarrow A_x[/math] — [math]k[/math]-большое.» Здесь, опять же, глупый момент. Нам нужно ведь не только что оно в каком-то случае было б k-большим, но и чтобы в противном случае оно было бы k-маленьким, а этого и здесь не написано (хотя, стоит заметить, доказано).
   1. Не понял, если оно не [math]k[/math]-большое, то [math]k[/math]-маленькое, и в этом случае [math]x \not \in L[/math] как видно из эквивалентности [math]x \in L \Leftrightarrow A_x[/math] — [math]k[/math]-большое.
8. Предпоследняя строчка нечитабельна. Кажется, там 2 предложения, их стоит разнести по строчкам. Ну и в первом из них поставить где-нибудь скобочки, чтобы оно стало читаемым.