информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Страшный баг в WindowsСетевые кракеры и правда о деле Левина
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





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

У Кука есть доказательство NP-полноты задачи ВЫП.
Автор предлагает РЕШЕНИЕ этой задачи, предполагая, что оно полиномиально.

Теперь попробуйте определиться, что вы хотите знать: является ли задача ВЫП NP-полной или является ли предложенный алгоритм полиномиальным?
<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 Статус: Незарегистрированный пользователь
<"чистая" ссылка>
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach