Обсуждение:Теорема Махэни - История изменений

188.65.69.199: /* TODO 2 */

2012-05-11T18:55:57Z

‎TODO 2

188.65.69.199: * → #

2012-05-11T18:51:10Z

* → #

188.65.69.199: todo 2

2012-05-10T22:36:41Z

todo 2

Leugenea: todo

2012-04-29T13:44:44Z

todo

Новая страница

== TODO ==
* «…количество различных аргументов в формуле <tex>\phi</tex>.» У формулы нет аргументов.
* «Так как функция <tex>f</tex> работает полиномиальное время, и <tex>|\phi| = |y|</tex>…» Что значит <tex>|\phi| = |y|</tex>? Нужно чётко определенить, что такое «модуль формулы» и «модуль вектора», иначе дальше понять что-то невозможно.
Дальше всё более-менее, вроде как норм, но нужно посмотреть, как сочитается то, что я додумал, с твоими определниями «модуля формулы». Ну и кое-где орфография, я пока на это не обращал мнивания.

@@ Строка 9: / Строка 9: @@
 # Когда ты ссылаешь на «лемму два», лучше писать «лемма (2)».
 # «…что, начиная с некоторого <tex>i</tex>…» <tex>i</tex> — не самая лучшая буква в данном случае, потому что буквально через строчку ты используешь ту же букву <tex>i</tex>, но теперь она уже не имеет данного смысла. Чтобы избежать путаницы, выбери другую букву.
-# «Тогда по вышеуказанной причине <tex>x \notin [w_i, w_j]</tex>…» По какой такой причине? Я такой причины не нашёл. Видимо, имеется в виду, что <tex>x</tex> — это минимальное такая строка, но на этом в любом случае надо сделать какой-то акцент.
+# <s>«Тогда по вышеуказанной причине <tex>x \notin [w_i, w_j]</tex>…» По какой такой причине? Я такой причины не нашёл. Видимо, имеется в виду, что <tex>x</tex> — это минимальное такая строка, но на этом в любом случае надо сделать какой-то акцент.</s>
 # «…если <tex>w_0</tex> или <tex>w_1</tex> лежат в <tex>S</tex>…» Насколько я понимаю, в <tex>S</tex> у нас лежат <tex>z_i</tex>.
 # Я, конечно, понимаю, что <tex>k = O(nr)</tex> — это чисто математический факт, но чтобы его получить, мне понадобился листок бумаги и вспоминание ряда Тейлора для логарифма. В общем, его надо объяснить. Например, написать в скобках «это можно получить, выразив <tex>k</tex> через <tex>n</tex> и <tex>r</tex> и воспользовавшисть формулой Тейлора для логарифма» (здесь, разумеется, нужно сделать ссылку на нужную формулу в википедии, например).
-# «Таким образом, мы можем разрешить язык <tex>LSAT</tex> за полиномиальное время, найдя лексикографически минимальную строку…» Этот момент надо осветить подробней. Потому что… ну как бы мы сказали, что шагов «отсеивания» строк — полином. После — тоже полином. Но за кадром осталось, что на каждом шаге мы должны посчитать все <tex>z_i</tex>, а потом (что важно!) должны узнать, есть ли среди них одинаковые. Это всё не настолько тривиальный момент, чтобы всё это просто взять и опустить.
+# <s>«Таким образом, мы можем разрешить язык <tex>LSAT</tex> за полиномиальное время, найдя лексикографически минимальную строку…» Этот момент надо осветить подробней. Потому что… ну как бы мы сказали, что шагов «отсеивания» строк — полином. После — тоже полином. Но за кадром осталось, что на каждом шаге мы должны посчитать все <tex>z_i</tex>, а потом (что важно!) должны узнать, есть ли среди них одинаковые. Это всё не настолько тривиальный момент, чтобы всё это просто взять и опустить.</s>
 # Последнее предложение в доказательстве нужно выделить в отдельный абзац — это всё-таки некий вывод.
 # Пока правишь всё это, можешь не думать о грамотности, но прежде чем присылать заявку, проверь пунктуацию — у тебя продолбаны запятые, а кое-где даже тире.

@@ Строка 1: / Строка 1: @@
 == TODO ==
-* «…количество различных аргументов в формуле <tex>\phi</tex>.» У формулы нет аргументов.
+# «…количество различных аргументов в формуле <tex>\phi</tex>.» У формулы нет аргументов.
-* <s>«Так как функция <tex>f</tex> работает полиномиальное время, и <tex>|\phi| = |y|</tex>…» Что значит <tex>|\phi| = |y|</tex>? Нужно чётко определить, что такое «модуль формулы» и «модуль вектора», иначе дальше понять что-то невозможно.</s>
+# <s>«Так как функция <tex>f</tex> работает полиномиальное время, и <tex>|\phi| = |y|</tex>…» Что значит <tex>|\phi| = |y|</tex>? Нужно чётко определить, что такое «модуль формулы» и «модуль вектора», иначе дальше понять что-то невозможно.</s>
 Дальше всё более-менее, вроде как норм, но нужно посмотреть, как сочетается то, что я додумал, с твоими определениями «модуля формулы». Ну и кое-где орфография, я пока на это не обращал внивания.
 == TODO 2 ==
-* Слово «очевидно» не нужно употреблять по возможности. Как сказал АС: «Если читателю это неочевидно, он чувствует себя идиотом. Не надо делать из читателей идиотов.» Это я к тому, что мне приходится каждый раз полминуты думать, почему «Очевидно, что <tex>LSAT \in NP</tex>» очевидно. Напиши какое-нибудь пояснение.
+# Слово «очевидно» не нужно употреблять по возможности. Как сказал АС: «Если читателю это неочевидно, он чувствует себя идиотом. Не надо делать из читателей идиотов.» Это я к тому, что мне приходится каждый раз полминуты думать, почему «Очевидно, что <tex>LSAT \in NP</tex>» очевидно. Напиши какое-нибудь пояснение.
-* Глобально: ссылки на все определения всех классов языков, которые ты используешь. Подсказка: если текст в техе, то ссылку можно сделать сноской.
+# Глобально: ссылки на все определения всех классов языков, которые ты используешь. Подсказка: если текст в техе, то ссылку можно сделать сноской.
-* Когда ты ссылаешь на «лемму два», лучше писать «лемма (2)».
+# Когда ты ссылаешь на «лемму два», лучше писать «лемма (2)».
-* «…что, начиная с некоторого <tex>i</tex>…» <tex>i</tex> — не самая лучшая буква в данном случае, потому что буквально через строчку ты используешь ту же букву <tex>i</tex>, но теперь она уже не имеет данного смысла. Чтобы избежать путаницы, выбери другую букву.
+# «…что, начиная с некоторого <tex>i</tex>…» <tex>i</tex> — не самая лучшая буква в данном случае, потому что буквально через строчку ты используешь ту же букву <tex>i</tex>, но теперь она уже не имеет данного смысла. Чтобы избежать путаницы, выбери другую букву.
-* «Тогда по вышеуказанной причине <tex>x \notin [w_i, w_j]</tex>…» По какой такой причине? Я такой причины не нашёл. Видимо, имеется в виду, что <tex>x</tex> — это минимальное такая строка, но на этом в любом случае надо сделать какой-то акцент.
+# «Тогда по вышеуказанной причине <tex>x \notin [w_i, w_j]</tex>…» По какой такой причине? Я такой причины не нашёл. Видимо, имеется в виду, что <tex>x</tex> — это минимальное такая строка, но на этом в любом случае надо сделать какой-то акцент.
-* «…если <tex>w_0</tex> или <tex>w_1</tex> лежат в <tex>S</tex>…» Насколько я понимаю, в <tex>S</tex> у нас лежат <tex>z_i</tex>.
+# «…если <tex>w_0</tex> или <tex>w_1</tex> лежат в <tex>S</tex>…» Насколько я понимаю, в <tex>S</tex> у нас лежат <tex>z_i</tex>.
-* Я, конечно, понимаю, что <tex>k = O(nr)</tex> — это чисто математический факт, но чтобы его получить, мне понадобился листок бумаги и вспоминание ряда Тейлора для логарифма. В общем, его надо объяснить. Например, написать в скобках «это можно получить, выразив <tex>k</tex> через <tex>n</tex> и <tex>r</tex> и воспользовавшисть формулой Тейлора для логарифма» (здесь, разумеется, нужно сделать ссылку на нужную формулу в википедии, например).
+# Я, конечно, понимаю, что <tex>k = O(nr)</tex> — это чисто математический факт, но чтобы его получить, мне понадобился листок бумаги и вспоминание ряда Тейлора для логарифма. В общем, его надо объяснить. Например, написать в скобках «это можно получить, выразив <tex>k</tex> через <tex>n</tex> и <tex>r</tex> и воспользовавшисть формулой Тейлора для логарифма» (здесь, разумеется, нужно сделать ссылку на нужную формулу в википедии, например).
-* «Таким образом, мы можем разрешить язык <tex>LSAT</tex> за полиномиальное время, найдя лексикографически минимальную строку…» Этот момент надо осветить подробней. Потому что… ну как бы мы сказали, что шагов «отсеивания» строк — полином. После — тоже полином. Но за кадром осталось, что на каждом шаге мы должны посчитать все <tex>z_i</tex>, а потом (что важно!) должны узнать, есть ли среди них одинаковые. Это всё не настолько тривиальный момент, чтобы всё это просто взять и опустить.
+# «Таким образом, мы можем разрешить язык <tex>LSAT</tex> за полиномиальное время, найдя лексикографически минимальную строку…» Этот момент надо осветить подробней. Потому что… ну как бы мы сказали, что шагов «отсеивания» строк — полином. После — тоже полином. Но за кадром осталось, что на каждом шаге мы должны посчитать все <tex>z_i</tex>, а потом (что важно!) должны узнать, есть ли среди них одинаковые. Это всё не настолько тривиальный момент, чтобы всё это просто взять и опустить.
-* Последнее предложение в доказательстве нужно выделить в отдельный абзац — это всё-таки некий вывод.
+# Последнее предложение в доказательстве нужно выделить в отдельный абзац — это всё-таки некий вывод.
-* Пока правишь всё это, можешь не думать о грамотности, но прежде чем присылать заявку, проверь пунктуацию — у тебя продолбаны запятые, а кое-где даже тире.
+# Пока правишь всё это, можешь не думать о грамотности, но прежде чем присылать заявку, проверь пунктуацию — у тебя продолбаны запятые, а кое-где даже тире.