Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Насколько я понимаю в классах сложности, NP-полные задачи... 29.12.04 13:11 Число просмотров: 4023
Автор: 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-нотации это утверждение неверно.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
