Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Полиномиальный алгоритм для задачи ВЫП 17.02.05 19:14 Число просмотров: 3695
Автор: Партизан Статус: Незарегистрированный пользователь
|
> Решение проблемы NP-полноты заключается в отыскании
> полиномиального алгоритма для решения любой из NP-полных
> задач в общем виде.
В статье "NP-полнота, суперприведение и проблема четырёх красок" приведён полиномиальный алгоритм для решения задачи ВЫП и показано, что для ответа о выполнимости или невыполнимости нужно просмотреть таблицу не более m раз, где m - число строк в таблице ВЫП.
> Т.е. для доказательства надо
> представить алгоритм и показать, что рост его сложности не
> экспоненциален по входным данным для задачи любого вида.
Другие NP-полные задачи полиномиально сводятся к ВЫП.
> Представить алгоритм для единственной задачи частного вида
> - это не проблема.
Там представлен алгоритм для задачи ВЫП общего вида.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
