> > вообще-то он полиномиальный.. > > хотя с другой стороны - он вероятностный, и к тому же > > тест.. а речь вроде шла о факторизации.. > > Но этот тест можна рассматривать как подзадачу задачи > факторизации...
во-первых нельзя (или что такое тогда "подзадача"??)..
во-вторых если даже и можно было, то что из этого следует?
Первый. В каком состоянии сейчас находится тема, упомянутая в заголовке? Возможно ли где-нибудь ознакомиться с результатами последних исследований в данной области (предпочтительны русскоязычные материалы). Уже достаточно давно встречаю в Сети подобные ресурсы: 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
> есть же вероятностный тест Шамиля-Рабина...и он, имхо, не > относится к НП полному классу...я не помню точно, но эта > шняга неплохо описана в Кормене "Алгоритмы:построение и > анализ"
вообще-то он полиномиальный..
хотя с другой стороны - он вероятностный, и к тому же тест.. а речь вроде шла о факторизации..
> > вообще-то он полиномиальный.. > > хотя с другой стороны - он вероятностный, и к тому же > > тест.. а речь вроде шла о факторизации.. > > Но этот тест можна рассматривать как подзадачу задачи > факторизации...
во-первых нельзя (или что такое тогда "подзадача"??)..
во-вторых если даже и можно было, то что из этого следует?
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
