информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Где водятся OGRыСтрашный баг в WindowsЗа кого нас держат?
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Крупный взлом GoDaddy 
 Просроченный сертификат ломает... 
 Phrack #70/0x46 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
http://arxiv.org/ftp/cs/papers/0610/0610125.pdf 26.10.06 11:38  Число просмотров: 3786
Автор: xx Статус: Незарегистрированный пользователь
<"чистая" ссылка>
<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-2021 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach