Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
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-полных?
|
|
|
подробно о проекте
Анализ криптографических сетевых...
