информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Портрет посетителяГде водятся OGRыSpanning Tree Protocol: недокументированное применение
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Простое пробивание рабочего/провайдерского... 
 400 уязвимостей в процессорах Snapdragon 
 Яндекс неуклюже оправдался за установку... 
главная обзор 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
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Насколько я понимаю в классах сложности, NP-полные задачи... 29.12.04 13:11  Число просмотров: 3380
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> Признаю, с NP-полнотой я знаком лишь поверхностно и критика
> моя была обращена больше не в адрес статьи, а в адрес
> заключения, где приводились сведения о сложности
> факторизации. Насколько я понял вначале, смысл всей статьи
> к этому и сводился - так уж построено изложение. Обычно все
> выводы пишутся в конце, а там как раз сложность
> факторизации - а по данному вопросу в статье ничего
> конкретного не наблюдается.
Насколько я понимаю в классах сложности, NP-полные задачи это такие NP задачи, решение хотя бы одной из которых за полиномиальное время автоматически приводит к решению ВСЕХ NP-полных задач за полиномиальное же время. Чаще всего для доказательства NP-полноты задачи сводят к задаче выполнимости. Если сведение возможно за полиномиальное время (которое тоже следует включить в оценку сложности), то задача - NP-полная.

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

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

То бишь если говорить что f(x) = O(g(x)), то
limit(x = infinity, f(x) / g(x)) = 1;

> пределе, понятно)". Однако т. к. сложность возрастает
> быстрее чем x^2, то она естесственно будет возрастать
> быстрее чем x^0.5 - поэтому можно написать O(x^0.5) и
Неправильно. limit(x = infinity, (x ^ 2) / (x^0.5)) = infinity, а не 1. Следовательно говорить об эквивалентности O(x^2) и O(x^0.5) не следует

> формально это так же будет верно. Задача нахождения
> сложности таким образом сводится к нахождению самой
> быстрорастущей функции, которая растёт тем не менее
> медленнее, чем сложность. Ничего похожего на подобные
Исходя из неправильного понимания O-нотации это утверждение неверно.
<site updates> Поиск 








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


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