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