информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Все любят медСетевые кракеры и правда о деле ЛевинаПортрет посетителя
BugTraq.Ru
Русский BugTraq
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Модель надежности отказоустойчивой... 
 Oracle выпустила срочный патч для... 
 Атака на WPA2 
 Outlook полгода отправлял зашифрованные... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





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

Поясню на примере. Представим, что на основании ряда выводов мы говорим, что некоторая задача размера n имеет сложность n!. По традиции факториал имеет название "суперэкспонента", т.к. ассимптотически n! стремится к n^n.
А теперь кое-что интересное. Рассматривая рост сложности частного двух факториалов вроде как получается полином. Но при этом существует разложение некоторой экспоненты на конечную сумму таких полиномов, что, вроде как, доказывает P=NP, но при этом никаким образом не влияет на эффективность решения NP-полных задач.

Подобные сложности заставляют вводить новые классы для характеристики задач с пока неясным статусом.

В заключении хотелось бы сказать, что на мой личный взгляд задача факторизации - чистейшая NP полная задача, безо всяких скидок. Даже доказать смогу. :)
<theory> Поиск 








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


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