Выполните сокращение от Не Все равно 3SAT до SplittingSet
Я изучал редукцию и видел это упражнение, но не могу его решить. Кто-нибудь может дать мне несколько советов в правильном направлении? Сокращение происходит от Not All Equal 3SAT, где язык = {: T представляет собой набор троек T1, T2, T3... литералов над n булевыми переменными x1, x2, .,,, xn такой, что ∃b1, b2, b3, ... такой, что каждая тройка T i имеет истинный и ложный литерал}
и SplittingSet - это язык: {: S - это множество. M - это множество подмножеств S, где существует разбиение S на два подмножества S1 и S2, что позволяет не быть подмножеством в M, которое целиком содержится в S1 или S2.}
Я не могу понять, как я должен подходить к этой проблеме. Я знаю, как уменьшить проблему в целом, но эта действительно помогает мне!