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