P vs NP на примере задачи 3-SAT11.04.16 14:24 Автор: lime Статус: Незарегистрированный пользователь Отредактировано 11.04.16 14:27 Количество правок: 2
Представим, что мы научились делать с ней следующие преобразования:
1. Мы можем разделить все множество переменных, на которых определена формула, на два непересекающихся подмножества. Первое подмножество будет называться "базисным" и содержать базисные переменные, второе - "определяемым" и содержать определяемые переменные.
Что это значит? Очевидно, что инициализация значений одной или нескольких переменных формулы 3-SAT приводит к тому, что мы вынужденно определяем значения другой (или нескольких других) переменных. Вот именно на этом основании мы и делим все множество переменных на две группы. Базисная группа будет содержать переменные, значения которых мы можем определить произвольно на свое усмотрение. Определяемая группа содержит те переменные, значения которых определяет инициализация некоторого подмножества переменных из "базисного" множества.
2. Имея два данных множества мы научились аналитически в компактном виде формулировать зависимости для каждой переменной определяемого множества от значений переменных базисного множества.
Очевидно, что в данном случае соотношение, заявленное в заголовке будет иметь вид P=NP.
Вопрос. А если исходная формула 3-SAT будет сводиться к описанному выше виду, но с одной оговоркой: в качестве дополнительного ограничения к ней будет добавлена формула 2-SAT, можно ли будет говорить о том, что таким образом сформулированная задача уже должна быть отнесена к классу NP-полных?
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
