информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Все любят медАтака на InternetSpanning Tree Protocol: недокументированное применение
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
вообще-то он полиномиальный.. 12.07.04 08:40  Число просмотров: 2921
Автор: zelych Статус: Member
<"чистая" ссылка>

> есть же вероятностный тест Шамиля-Рабина...и он, имхо, не
> относится к НП полному классу...я не помню точно, но эта
> шняга неплохо описана в Кормене "Алгоритмы:построение и
> анализ"

вообще-то он полиномиальный..
хотя с другой стороны - он вероятностный, и к тому же тест.. а речь вроде шла о факторизации..
<theory>
Проблема 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
<"чистая" ссылка>
> > вообще-то он полиномиальный..
> > хотя с другой стороны - он вероятностный, и к тому же
> > тест.. а речь вроде шла о факторизации..
>
> Но этот тест можна рассматривать как подзадачу задачи
> факторизации...


во-первых нельзя (или что такое тогда "подзадача"??)..
во-вторых если даже и можно было, то что из этого следует?
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach