Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Проблема NP полноты. 15.06.04 11:26 Число просмотров: 2275
Автор: lime Статус: Незарегистрированный пользователь
|
Интересует два вопроса.
Первый. В каком состоянии сейчас находится тема, упомянутая в заголовке? Возможно ли где-нибудь ознакомиться с результатами последних исследований в данной области (предпочтительны русскоязычные материалы). Уже достаточно давно встречаю в Сети подобные ресурсы: http://www.tarusa.ru/~mit/RUS/rus.php, но, к сожалению, не вижу результата подобных заявлений.
Второй.
Интересует задача факторизации больших чисел и ее соотношение с классом NP-полных задач. На вышеупомянутом ресурсе по данной ссылке http://www.tarusa.ru/~mit/RUS/crypt.php можно найти информацию о том, что задача факторизации и NP-полные задачи (приведен пример задачи ВЫПОЛНИМОСТЬ) имеют одинаковый порядок роста сложности по входным данным. На основании этого косвенно можно предположить, что задача факторизации является NP-полной. Кто-нибудь занимается или занимался вопросами доказательства отнесения задачи факторизации к классу NP-полных задач?
|
- Проблема NP полноты. - lime 15.06.04 11:26 [2275]
|
|
|