Итак, я получил этот домашний вопрос, и нас просят свести проблему выполнимости k-независимого набора к 3-SAT набору предложений в конъюнктивной нормальной форме.
Итак, для G (V, E) у нас установлены вершины
V = { x1, x2, x3, x4, x5, x6}
и набор ребер
E = {e1 = (x1, x3), e2 = (x1, x5), e3 = (x1, x6), e4 = (x2, x5), e5 = (x2, x6), e6 = (x3, x4), e7 = (x3, x5), e8 = (x5, x6)}
Мой первый подход к этому состоит в том, чтобы иметь предложение для каждого ребра, поскольку у нас не может быть ребра между двумя вершинами в независимом наборе:
e1: (¬x1 v ¬x3)
e2: (¬x1 v ¬ x5)
e3: (¬x1 v ¬x6)
e4: (¬x2 v ¬x5)
e5: (¬x2 v ¬x6)
e6: (¬x3 v ¬x4)
e7: (¬x3 v ¬x5)
e8: (¬x5 v ¬x6)
Но проблема в том, например, для k = 3, как писать предложения, чтобы гарантировать, что По крайней мере, для трех различных переменных (xi) установлено значение true?
Это достижимо с использованием взвешенной-2-выполнимости, но, кажется, трудно достичь, просто используя старый добрый 3-SAT.
Есть какие-нибудь подсказки, как действовать?
