Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Эта задача уже несколько лет классифицируется как... 30.09.04 14:37 Число просмотров: 4326
Автор: lime Статус: Незарегистрированный пользователь
|
> Во фразе "NP-полнота неизвестна" я имел в виду то, что до
> сих пор не известно к какому классу сложности относится
> задача факторизации. Более того, многие уверены в том, что
> эта задача не является NP-полной.
Эта задача уже несколько лет классифицируется как относящаяся к классу CoNp. Это такой класс, который характеризует исключительно рост сложности задачи и ничто больше. В нашем смысле (прикладном, не вдаваясь в особенности) этого достаточно.
Может возникнуть резонный вопрос типа следующего "есть полиномиальный рост, а есть экспоненциальный, что же может существовать еще?". Оказывается есть еще множество функций, которые напрочь отрицают правильность такого подхода, когда рассматриваются только два данных класса. До сих пор остается очень трудный вопрос о некоторых функциях. Основная из них - факториал.
Поясню на примере. Представим, что на основании ряда выводов мы говорим, что некоторая задача размера n имеет сложность n!. По традиции факториал имеет название "суперэкспонента", т.к. ассимптотически n! стремится к n^n.
А теперь кое-что интересное. Рассматривая рост сложности частного двух факториалов вроде как получается полином. Но при этом существует разложение некоторой экспоненты на конечную сумму таких полиномов, что, вроде как, доказывает P=NP, но при этом никаким образом не влияет на эффективность решения NP-полных задач.
Подобные сложности заставляют вводить новые классы для характеристики задач с пока неясным статусом.
В заключении хотелось бы сказать, что на мой личный взгляд задача факторизации - чистейшая NP полная задача, безо всяких скидок. Даже доказать смогу. :)
|
|
|
подробно о проекте
Анализ криптографических сетевых...
