Обсуждение:Теорема Лаутемана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(ToDo 2)
 
Строка 20: Строка 20:
 
== ToDo 2 ==
 
== ToDo 2 ==
 
# Почему нет ссылок? На BPP, например? А, я нашёл их! Но сделай их лучше референсами. Как это делается, посмотри, например, у Иры в конспекте.
 
# Почему нет ссылок? На 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>R(x,y)</tex>? Откуда оно вообще взялось?
 
# «Таким образом, необходимо уметь записывать «существует много» с помощью кванторов…» Это всё-таки перечисление, а перечисление пишется через запятую.
 
# «Таким образом, необходимо уметь записывать «существует много» с помощью кванторов…» Это всё-таки перечисление, а перечисление пишется через запятую.
 
# «Если <tex>|X| < \frac{2^t}{k}</tex>, то <tex>X</tex> является <tex>k</tex>-маленьким.» Эээ… нет, X называется k-маленьким, если оно не k-большое. А это какое-то второе определение, причём эквивалентность этих определений нигде не доказана.
 
# «Если <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>\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 предложения, их стоит разнести по строчкам. Ну и в первом из них поставить где-нибудь скобочки, чтобы оно стало читаемым.
 
# Предпоследняя строчка нечитабельна. Кажется, там 2 предложения, их стоит разнести по строчкам. Ну и в первом из них поставить где-нибудь скобочки, чтобы оно стало читаемым.

Текущая версия на 15:38, 4 июня 2012

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 предложения, их стоит разнести по строчкам. Ну и в первом из них поставить где-нибудь скобочки, чтобы оно стало читаемым.