Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Проблема NP полноты. 15.06.04 11:26
Автор: lime Статус: Незарегистрированный пользователь
|
Интересует два вопроса.
Первый. В каком состоянии сейчас находится тема, упомянутая в заголовке? Возможно ли где-нибудь ознакомиться с результатами последних исследований в данной области (предпочтительны русскоязычные материалы). Уже достаточно давно встречаю в Сети подобные ресурсы: http://www.tarusa.ru/~mit/RUS/rus.php, но, к сожалению, не вижу результата подобных заявлений.
Второй.
Интересует задача факторизации больших чисел и ее соотношение с классом NP-полных задач. На вышеупомянутом ресурсе по данной ссылке http://www.tarusa.ru/~mit/RUS/crypt.php можно найти информацию о том, что задача факторизации и NP-полные задачи (приведен пример задачи ВЫПОЛНИМОСТЬ) имеют одинаковый порядок роста сложности по входным данным. На основании этого косвенно можно предположить, что задача факторизации является NP-полной. Кто-нибудь занимается или занимался вопросами доказательства отнесения задачи факторизации к классу NP-полных задач?
|
|
кажется, так оно и есть..
22.06.04 20:42
Автор: zelych Статус: Member
|
> одинаковый порядок роста сложности по входным данным. На
> основании этого косвенно можно предположить, что задача
> факторизации является NP-полной. Кто-нибудь занимается или
кажется, так оно и есть..
и логарифмирование - тоже..
|
| |
кажется, так оно и есть.. 12.07.04 02:06
Автор: Memphis Статус: Незарегистрированный пользователь
|
> > одинаковый порядок роста сложности по входным данным.
> На
> > основании этого косвенно можно предположить, что
> задача
> > факторизации является NP-полной. Кто-нибудь занимается
> или
>
> кажется, так оно и есть..
> и логарифмирование - тоже..
есть же вероятностный тест Шамиля-Рабина...и он, имхо, не относится к НП полному классу...я не помню точно, но эта шняга неплохо описана в Кормене "Алгоритмы:построение и анализ"
|
| | |
вообще-то он полиномиальный..
12.07.04 08:40
Автор: zelych Статус: Member
|
> есть же вероятностный тест Шамиля-Рабина...и он, имхо, не
> относится к НП полному классу...я не помню точно, но эта
> шняга неплохо описана в Кормене "Алгоритмы:построение и
> анализ"
вообще-то он полиномиальный..
хотя с другой стороны - он вероятностный, и к тому же тест.. а речь вроде шла о факторизации..
|
| | | |
НО.. 13.07.04 14:17
Автор: Memphis Статус: Незарегистрированный пользователь
|
> вообще-то он полиномиальный..
> хотя с другой стороны - он вероятностный, и к тому же
> тест.. а речь вроде шла о факторизации..
Но этот тест можна рассматривать как подзадачу задачи факторизации...
|
| | | | |
бред.. 13.07.04 16:11
Автор: zelych Статус: Member
|
> > вообще-то он полиномиальный..
> > хотя с другой стороны - он вероятностный, и к тому же
> > тест.. а речь вроде шла о факторизации..
>
> Но этот тест можна рассматривать как подзадачу задачи
> факторизации...
во-первых нельзя (или что такое тогда "подзадача"??)..
во-вторых если даже и можно было, то что из этого следует?
|
|
|
подробно о проекте
Анализ криптографических сетевых...
