Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Ответ (долгожданный) 28.12.04 18:03 Число просмотров: 3570
Автор: Heller <Heller> Статус: Elderman
|
Признаю, с NP-полнотой я знаком лишь поверхностно и критика моя была обращена больше не в адрес статьи, а в адрес заключения, где приводились сведения о сложности факторизации. Насколько я понял вначале, смысл всей статьи к этому и сводился - так уж построено изложение. Обычно все выводы пишутся в конце, а там как раз сложность факторизации - а по данному вопросу в статье ничего конкретного не наблюдается.
Далее, вы говорите, что асимптотика видна из таблицы. Не согласен категорически - из таблицы не видноничего Это то же самое что строить график синуса в точках pi*n и утверждать, что данная функция константа.
По поводу ассимтотики. Если разобраться, то "сложность=O(x^2)" означает ни что иное, как "сложность возрастает при возратании x быстрее чем функция x^2 (в пределе, понятно)". Однако т. к. сложность возрастает быстрее чем x^2, то она естесственно будет возрастать быстрее чем x^0.5 - поэтому можно написать O(x^0.5) и формально это так же будет верно. Задача нахождения сложности таким образом сводится к нахождению самой быстрорастущей функции, которая растёт тем не менее медленнее, чем сложность. Ничего похожего на подобные рассуждения я в статье не увидел (опять же обращаю внимание, что статья построена таким образом, что складывается впечатление, что вся её цель - показать сложность факторизации).
Вот, вроде как на основные вопросы высказался. Итог - статью объективно оценить я не в состоянии, а вот за Литературный талант двойку :-) Сама организация статьи наталкивает на мысли о факторизации - она написана таким образом, что сложность факторизации кажется всей целью, а, как видно из Вашего ответа, это не совсем так.
Ещё хочу извиниться за столь позний ответ - работы куча, а что бы писать о математике требуется время. Поэтому не отвечал.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
