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





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
P vs NP на примере задачи 3-SAT 11.04.16 14:24  
Автор: lime Статус: Незарегистрированный пользователь
Отредактировано 11.04.16 14:27  Количество правок: 2
<"чистая" ссылка>
Задача. Дана формула 3-SAT в общем виде.

Представим, что мы научились делать с ней следующие преобразования:

1. Мы можем разделить все множество переменных, на которых определена формула, на два непересекающихся подмножества. Первое подмножество будет называться "базисным" и содержать базисные переменные, второе - "определяемым" и содержать определяемые переменные.

Что это значит? Очевидно, что инициализация значений одной или нескольких переменных формулы 3-SAT приводит к тому, что мы вынужденно определяем значения другой (или нескольких других) переменных. Вот именно на этом основании мы и делим все множество переменных на две группы. Базисная группа будет содержать переменные, значения которых мы можем определить произвольно на свое усмотрение. Определяемая группа содержит те переменные, значения которых определяет инициализация некоторого подмножества переменных из "базисного" множества.

2. Имея два данных множества мы научились аналитически в компактном виде формулировать зависимости для каждой переменной определяемого множества от значений переменных базисного множества.

Очевидно, что в данном случае соотношение, заявленное в заголовке будет иметь вид P=NP.

Вопрос. А если исходная формула 3-SAT будет сводиться к описанному выше виду, но с одной оговоркой: в качестве дополнительного ограничения к ней будет добавлена формула 2-SAT, можно ли будет говорить о том, что таким образом сформулированная задача уже должна быть отнесена к классу NP-полных?
1






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


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