Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Да, это очень хороший пример. Большей воды я не встречал. 03.02.05 09:49 Число просмотров: 3784
Автор: 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
Вот как раз по этому адресу я отправил свой вопрос. О результатах сообщил выше. :)
|
|
|