информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Портрет посетителяSpanning Tree Protocol: недокументированное применение
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор 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-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach