Еще одна работа на тему, заявленную в заголовке, о чем автор данной статьи явно и недвусмысленно заявляет в статье. Пока только начал разбираться, говорить ничего не буду, но сама система, скажем так, нетривиальна, поэтому есть подозрение, что просто в лесу белку не заметили. Желающие найти эту белку приглашаются на охоту... :)
Нашел? :) А есть ссылки на коректное и признаное...10.12.06 23:00 Автор: MadBinom Статус: Незарегистрированный пользователь
> http://zhurnal.gpi.ru/articles/2005/101.pdf > > Еще одна работа на тему, заявленную в заголовке, о чем > автор данной статьи явно и недвусмысленно заявляет в > статье. Пока только начал разбираться, говорить ничего не > буду, но сама система, скажем так, нетривиальна, поэтому > есть подозрение, что просто в лесу белку не заметили. > Желающие найти эту белку приглашаются на охоту... :) Нашел? :) А есть ссылки на коректное и признаное доказательство нп-полноты решаемой задачи?
Если я правильно понял вопрос, то вы хотите, чтобы я...22.12.06 15:29 Автор: lime Статус: Незарегистрированный пользователь
> Почитайте Кука. Именно он утверждал, что ВЫП NP-полна. И, > кстати, так уж сложилось, что это первая из задач, для > которой это было доказано. У Кука есть доказательство NP-полноты задачи построения неортодоксальной графо-комбинаторной модели для задачи 3-ВЫПОЛНИМОСТИ? . собственно, автор статьи решает именно эту задачу:
...В работе рассмотрена неортодоксальная графо-комбинаторная модель для клас-
сической трудноразрешимой задачи 3-ВЫПОЛНИМОСТЬ и эффективный (полиноми-
альный) алгоритм построения этой модели. Предложенный метод анализа булевой
формулы выявляет возможность классификации формулы в широком диапазоне ее па-
раметров, характеризующих "размер входа" задачи...
У Кука есть доказательство NP-полноты задачи ВЫП.04.01.07 08:41 Автор: lime Статус: Незарегистрированный пользователь
> У Кука есть доказательство NP-полноты задачи построения > неортодоксальной графо-комбинаторной модели для задачи > 3-ВЫПОЛНИМОСТИ? . собственно, автор статьи решает именно > эту задачу: > ...В работе рассмотрена неортодоксальная графо-комбинаторная модель для классической > трудноразрешимой задачи 3-ВЫПОЛНИМОСТЬ и эффективный (полиномиальный) > алгоритм построения этой модели. Предложенный метод > анализа булевой формулы выявляет возможность классификации формулы в > широком диапазоне ее параметров, характеризующих "размер входа" задачи...
У Кука есть доказательство NP-полноты задачи ВЫП.
Автор предлагает РЕШЕНИЕ этой задачи, предполагая, что оно полиномиально.
Теперь попробуйте определиться, что вы хотите знать: является ли задача ВЫП NP-полной или является ли предложенный алгоритм полиномиальным?
http://arxiv.org/ftp/cs/papers/0610/0610125.pdf26.10.06 11:38 Автор: xx Статус: Незарегистрированный пользователь
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
