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