Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
У Кука есть доказательство NP-полноты задачи ВЫП. 04.01.07 08:41 Число просмотров: 4328
Автор: lime Статус: Незарегистрированный пользователь
|
> У Кука есть доказательство NP-полноты задачи построения
> неортодоксальной графо-комбинаторной модели для задачи
> 3-ВЫПОЛНИМОСТИ? . собственно, автор статьи решает именно
> эту задачу:
> ...В работе рассмотрена неортодоксальная графо-комбинаторная модель для классической > трудноразрешимой задачи 3-ВЫПОЛНИМОСТЬ и эффективный (полиномиальный)
> алгоритм построения этой модели. Предложенный метод
> анализа булевой формулы выявляет возможность классификации формулы в
> широком диапазоне ее параметров, характеризующих "размер входа" задачи...
У Кука есть доказательство NP-полноты задачи ВЫП.
Автор предлагает РЕШЕНИЕ этой задачи, предполагая, что оно полиномиально.
Теперь попробуйте определиться, что вы хотите знать: является ли задача ВЫП NP-полной или является ли предложенный алгоритм полиномиальным?
|
- P=NP? - lime 19.05.06 07:08 [3526]
|
|
|
подробно о проекте
Анализ криптографических сетевых...
У Кука есть доказательство NP-полноты задачи ВЫП. - lime