информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Где водятся OGRыSpanning Tree Protocol: недокументированное применение
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Google закрывает безлимитные Photos 
 Имя компании как средство XSS-атаки 
 Утекший код XP и Windows Server... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / site updates
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Ответ (долгожданный) 28.12.04 18:03  Число просмотров: 2901
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
Признаю, с NP-полнотой я знаком лишь поверхностно и критика моя была обращена больше не в адрес статьи, а в адрес заключения, где приводились сведения о сложности факторизации. Насколько я понял вначале, смысл всей статьи к этому и сводился - так уж построено изложение. Обычно все выводы пишутся в конце, а там как раз сложность факторизации - а по данному вопросу в статье ничего конкретного не наблюдается.

Далее, вы говорите, что асимптотика видна из таблицы. Не согласен категорически - из таблицы не видноничего Это то же самое что строить график синуса в точках pi*n и утверждать, что данная функция константа.

По поводу ассимтотики. Если разобраться, то "сложность=O(x^2)" означает ни что иное, как "сложность возрастает при возратании x быстрее чем функция x^2 (в пределе, понятно)". Однако т. к. сложность возрастает быстрее чем x^2, то она естесственно будет возрастать быстрее чем x^0.5 - поэтому можно написать O(x^0.5) и формально это так же будет верно. Задача нахождения сложности таким образом сводится к нахождению самой быстрорастущей функции, которая растёт тем не менее медленнее, чем сложность. Ничего похожего на подобные рассуждения я в статье не увидел (опять же обращаю внимание, что статья построена таким образом, что складывается впечатление, что вся её цель - показать сложность факторизации).

Вот, вроде как на основные вопросы высказался. Итог - статью объективно оценить я не в состоянии, а вот за Литературный талант двойку :-) Сама организация статьи наталкивает на мысли о факторизации - она написана таким образом, что сложность факторизации кажется всей целью, а, как видно из Вашего ответа, это не совсем так.

Ещё хочу извиниться за столь позний ответ - работы куча, а что бы писать о математике требуется время. Поэтому не отвечал.
<site updates> Поиск 








Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2020 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach