Изменения

Перейти к: навигация, поиск

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

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

Навигация