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





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Да, это очень хороший пример. Большей воды я не встречал. 03.02.05 09:49  Число просмотров: 2982
Автор: lime Статус: Незарегистрированный пользователь
Отредактировано 03.02.05 09:49  Количество правок: 1
<"чистая" ссылка>
> Какая Вам нужна реализация?
> http://www.tarusa.ru/~mit/RUS/sup_prim1.php:
> "На базе позиционной нотации доказано, что классы P и NP
> совпадают, создан программный продукт (ПП), который
> позволяет практически решать задачи из класса NP, но с
> трудностями, присущими уже классу P."
> Обратите внимание: говорится, что создан программный
> продукт.
> Там далее приведён пример.

Да, это очень хороший пример. Большей воды я не встречал.

Для начала. "Вот простой пример. Допустим спроектировано электронное устройство, состоящее из трех блоков, каждый из которых содержит 50 элементов и соединен с последующим посредством трех общих элементов. Представим данное устройство в логическом виде в форме задачи ВЫП. "
Хочу сказать, что это не простой пример хотя бы потому, что я не могу понять при чем здесь "электронное устройиство...из трех блоков". Не проще ли показать простую формулу ВЫП.


Далее.
"Каков результат применения суперприведения? 1) Сокращен размер исходной КНФ более, чем в 2 раза, а значит и размер самого электронного устройства. При этом выполняющие наборы не изменились, т.е. не изменился проектный замысел устройства. 2) В результате выполненной реструктуризации выполняющие наборы будут срабатывать по мере поступления запроса на них, т.е. полностью исключается время обработки холостых или подготовительных вычислений, какие имели бы место в исходном варианте. А это уже даст многократный прирост скорости работы по сравнению с исходным вариантом. "
Это, извините, не решение задачи ВЫП, а минимизация логической формулы. :)

И в заключении.
Решение проблемы NP-полноты заключается в отыскании полиномиального алгоритма для решения любой из NP-полных задач в общем виде. Т.е. для доказательства надо представить алгоритм и показать, что рост его сложности не экспоненциален по входным данным для задачи любого вида. Представить алгоритм для единственной задачи частного вида - это не проблема.
По поводу "программного продукта". Я его не видел и не работал с ним. А на слово я верить не буду.

И последнее. С трудом верится, что люди имеющие, по их словам методику решения, стОящую по авторитетным оценкам сотни миллиардов долларов пытаются найти деньги на "продолжение работ", а зарабатывают продажей книг. :)

Это не научный подход. Скорее смахивает на дешевый журналистский PR, устроенный с целью поднять шумиху и выдоить из этой ситуации максимум.

Теперь по поводу Вашего вопроса, упомянутого в заголовке. Я не знаю. Вся обстановка, с которой это обставлено, не располагает меня разбираться с этим вопросом. Но по "мебелировке" можно сделать вывод, что ответ будет скорее нет, чем да. Я пожалуй ознакомился бы с простым и понятным примером решения задачи ВЫП, изложенным ясно и без "электронных устройств на три блока", но его к сожалению нет.

> В книге (купить можно по этой ссылке:
> http://urss.ru/cgi-bin/db.pl?page=Book&id=24175&lang=Ru)
> тоже говорится о программных продуктах (см. параграф 8.14),
> которые, как я понимаю, созданы А. А. Фоминым. Спросить о
> них, как я понимаю, можно по адресу mit@tarusa.ru

Вот как раз по этому адресу я отправил свой вопрос. О результатах сообщил выше. :)
<site updates> Поиск 








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


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