Обсуждение:Теорема Махэни

TODO

1. «…количество различных аргументов в формуле [math]\phi[/math].» У формулы нет аргументов.
2. «Так как функция [math]f[/math] работает полиномиальное время, и [math]|\phi| = |y|[/math]…» Что значит [math]|\phi| = |y|[/math]? Нужно чётко определить, что такое «модуль формулы» и «модуль вектора», иначе дальше понять что-то невозможно.

Дальше всё более-менее, вроде как норм, но нужно посмотреть, как сочетается то, что я додумал, с твоими определениями «модуля формулы». Ну и кое-где орфография, я пока на это не обращал внивания.

TODO 2

1. Слово «очевидно» не нужно употреблять по возможности. Как сказал АС: «Если читателю это неочевидно, он чувствует себя идиотом. Не надо делать из читателей идиотов.» Это я к тому, что мне приходится каждый раз полминуты думать, почему «Очевидно, что [math]LSAT \in NP[/math]» очевидно. Напиши какое-нибудь пояснение.
2. Глобально: ссылки на все определения всех классов языков, которые ты используешь. Подсказка: если текст в техе, то ссылку можно сделать сноской.
3. Когда ты ссылаешь на «лемму два», лучше писать «лемма (2)».
4. «…что, начиная с некоторого [math]i[/math]…» [math]i[/math] — не самая лучшая буква в данном случае, потому что буквально через строчку ты используешь ту же букву [math]i[/math], но теперь она уже не имеет данного смысла. Чтобы избежать путаницы, выбери другую букву.
5. «Тогда по вышеуказанной причине [math]x \notin [w_i, w_j][/math]…» По какой такой причине? Я такой причины не нашёл. Видимо, имеется в виду, что [math]x[/math] — это минимальное такая строка, но на этом в любом случае надо сделать какой-то акцент.
6. «…если [math]w_0[/math] или [math]w_1[/math] лежат в [math]S[/math]…» Насколько я понимаю, в [math]S[/math] у нас лежат [math]z_i[/math].
7. Я, конечно, понимаю, что [math]k = O(nr)[/math] — это чисто математический факт, но чтобы его получить, мне понадобился листок бумаги и вспоминание ряда Тейлора для логарифма. В общем, его надо объяснить. Например, написать в скобках «это можно получить, выразив [math]k[/math] через [math]n[/math] и [math]r[/math] и воспользовавшисть формулой Тейлора для логарифма» (здесь, разумеется, нужно сделать ссылку на нужную формулу в википедии, например).
8. «Таким образом, мы можем разрешить язык [math]LSAT[/math] за полиномиальное время, найдя лексикографически минимальную строку…» Этот момент надо осветить подробней. Потому что… ну как бы мы сказали, что шагов «отсеивания» строк — полином. После — тоже полином. Но за кадром осталось, что на каждом шаге мы должны посчитать все [math]z_i[/math], а потом (что важно!) должны узнать, есть ли среди них одинаковые. Это всё не настолько тривиальный момент, чтобы всё это просто взять и опустить.
9. Последнее предложение в доказательстве нужно выделить в отдельный абзац — это всё-таки некий вывод.
10. Пока правишь всё это, можешь не думать о грамотности, но прежде чем присылать заявку, проверь пунктуацию — у тебя продолбаны запятые, а кое-где даже тире.