MIN-2-XOR-SAT и MAX-2-XOR-SAT: они NP-сложные?

13

Какова сложность MIN-2-XOR-SAT и MAX-2-XOR-SAT ? Они в П? Они NP-хард?

Чтобы формализовать это более точно, пусть

Φ(x)=inCi,

где x=(x1,,xm) и каждое предложение Ci имеет вид (xixj) или (xi¬xj) .

Задача 2-XOR-SAT состоит в том, чтобы найти присваивание x , удовлетворяющее Φ . Эта задача находится в P , так как она соответствует системе линейных уравнений mod 2 .

Задача MAX-2-XOR-SAT состоит в том, чтобы найти присваивание x которое максимизирует количество удовлетворенных предложений. Задача MIN-2-XOR-SAT состоит в том, чтобы найти назначение для x которое минимизирует количество удовлетворяемых предложений. Каковы сложности этих проблем?

Вдохновленный MIN или MAX-True-2-XOR-SAT NP-hard?

DW
источник

Ответы:

6

Извините за ответ на старый пост

(xixj)

G

Например:

(x1x2)(x1x3)(x2x3)(x1x4)

У нас есть такой график:

Grafo No Bipartito

это не двудольный

Есть три условия, которые являются выполнимыми, и поэтому мы должны просто устранить преимущество

kk

Для сокращения мы просто создаем новый литерал для каждой вершины и создаем для каждого ребра предложение, соединяющее два литерала.

Например:

У нас есть этот график,

Grafo No Bipartito 2

(x1x2)(x1x4)(x2x4)(x2x3)(x4x5)(x3x5)

kk

rotia
источник
1
Вы должны сделать это явно: поскольку MAX-CUT является NP-Hard, сокращение до MAX-XORSAT означает, что это также NP-Hard.
Сурьма
-1

(xixj)xixixjxixjxixj Истинно, если соответствующим вершинам в графе назначены разные цвета.

Если все вершины графа можно раскрасить, используя 2 цвета, и ни одна из двух вершин с общим краевым участком не будет присвоена один и тот же цвет, тогда уравнение выполнимо.

Но граф 2-раскрашивается тогда и только тогда, когда это двудольный граф. И определение, является ли граф двудольным, может быть сделано за полиномиальное время. Поэтому проблема в P, потому что если мы можем определить за полиномиальное время, что граф является двудольным графом, то он разрешим, в противном случае он не разрешим.

jcod0
источник
1
(xixj)(xk¬xl)k,l(xk¬xl)
2
Это подводит меня к более серьезной проблеме с вашим ответом. Проблема не в том, чтобы определить, является ли формула выполнимой; проблема состоит в том, чтобы определить назначение, которое удовлетворяет максимальному / минимальному количеству предложений. Ваш алгоритм только проверяет, является ли формула выполнимой. Таким образом, он решает 2-XOR-SAT, но не решает MIN-2-XOR-SAT или MAX-2-XOR-SAT - но я уже знал, что 2-XOR-SAT находится в P, как объяснено в вопрос. Я что-то не так понял?
DW
xixk
1
Но я до сих пор не понимаю, как это решает мой второй комментарий. Вы решили частный случай проблемы, о которой я не спрашивал. Короче говоря, этот ответ не отвечает на вопрос, который я задал.
DW