Сокращение от VC до {A, K |A - 3DNF (дизъюнктивная нормальная форма), и существует назначение, удовлетворяющее ровно k предложения в a}

Question

У меня есть следующий вопрос:

\ begin {align} L_2={a, k \ \ mid \ text {a - 3dnf (дизъюнктивная нормальная форма) и} \\ \ Text {Существует присвоение $ Z $, удовлетворяющее ровно $ K $ clauses в} A \} \ end {align}

Я знаю, что $ l_2 \ in $ NPC.

Показать, что $ l_2 \ in $ np относительно прост, я пропущу эту деталь.

Я стараюсь показать, что $ l_2 \ in $ NPC, используя уменьшение от VC $ \ leq_p l_2 $ (VC - крышка вершины, которую мы знаем в его NPC)

Я определил следующую функцию $ f $ :

$$ f (g, k)= (a, k) $$

Я подумал о том, что для каждого узла $ i $ в $ g $ будет определять Литерал $ x_i $ и сделать его в формате 3DNF, $ A=Bigvee (X_I \ quced x_i \ quce x_i) $ где $ 1 \ leq i \ leq n $ где $ n $ - это количество Узлы в $ g $ . Мы можем определить, что после $ z $ такое, что $ z $ Сыжается точно $ k $ clauses, просто дайте $ '1' $ Литерал $ x_i $ Так что узел $ i $ находится в VC, а $ '0' $ в противном случае, так Такой $ z $ существует.

Так легко увидеть, что $ (g, k) \ in $ vc $ \ Предполагается (a, k) \ in l_2 $ поскольку мы явно показали такое $ Z $ , который имеет смысл точно $ K $ пункты.

Но я не уверен, что другая сторона держит $ (g, k) \ not \ in \ in $ vc $ \ подразумевает (a, k) \ not \ in \ in l_2 $ Мы дали график, который не имеет VC в размере $ K $ Но я думаю, что к моему зданию ( $ a=bigvee (x_i \ enge x_i \ quce x_i) $ ) Мы можем найти $ z $ , который точно сохраняет $ k $ пункты (на самом деле мы можем найти $ Z $ , что Защищает $ x $ clauses, где $ 1 \ leq x \ leq n $ где $ n $ - это количество узлов в $ g $ .

Так что мое сокращение не держит?

Answer 1

Причина того, почему у вас возникли проблемы, потому что ваше решение не работает. В частности, проблема в том, что ваша формула не захватывает оператор задачи VC. Точнее, формула, которую вы создаете, всегда имеет задания, удовлетворяющие «$ K $ Представления, просто настройки $ K $ Переменные правда и остальные до false.

Дайте $ g= (v, e) $ Быть графиком и $ x \ subsEtqu v $ Быть VC в $ G $ . Тогда для любого края $ VW \ в E $ У нас должен быть $ V \ in x $ или $ W \ in x $ , предоставляя нам 3 взаимоисключающих возможности (по сути перезаписывающим $ v \ vee w $ в Dnf):

.
• $ v \ в x $ но $ W \ Notin x $ ,
• $ v \ notin x $ Но $ W \ in x $
• $ v \ in x $ и $ W \ in x $

Следовательно, края $ vw $ охватывается $ x $ Если и только если формула $ \ psi (vw)= (v \ wedge w) \ vee (\ neg v \ wedge w) \ vee (v \ quctge \ neg w) $ имеет ровно один Удовлетворенное предложение (в соответствии с назначением, соответствующим $ x $ ).

Создание такой формулы для каждого края и принимая их диспозицию, мы получаем формулу DNF $$ \ psi ^ \ text {vc} (g)=bigvee_ {e \ in e} \ psi (e)=bigvee_ {vw \ in} (v \ quild W) \ vee (\ neg v \ wedge w) \ vee (v \ wedge \ neg w) $$ И любое задание, удовлетворяющее ровно $ | E | $ clausees, должен быть VC $ G $ . Теперь нам нужен способ кодировать размер VC в него все, для чего мы можем повторно использовать свою идею. Определять $$ \ psi (g)=psi ^ \ pext {vc} (g) \ vee \ bigvee_ {v \ in v} v $$ И отметить, что количество удовлетворенных положений во второй части просто дается размером набора вершин, которые мы выбираем, поэтому общее количество удовлетворенных предложений под назначением, соответствующим некоторому VC $ X $ в $ g $ $ | E | + | X | $ .

Есть только одна проблема, оставаясь здесь. Мы могли бы получить задание, не соответствующий VC, но в том числе больше вершин, чтобы удовлетворить одинаковое количество пунктов, что желаемый VC. В качестве лекарства мы можем повторить первую формулу некоторые $ | V | + 1 $ Times Таким, что независимо от того, сколько вы выбрали вершины, общее количество удовлетворенных пунктов всегда будет слишком низким.

Следовательно, мы получаем окончательную формулу $$ \ psi ^ \ ast (g)=bigvee_ {i= 1} ^ {| v | + 1} \ psi ^ \ text {vc} (g) \ ve \ bigvee_ {v \ in v} v $$ И обратите внимание, что если $ g $ имеет VC $ x $ Тогда соответствующее задание удовлетворит ровно $ (| V | + 1) \ CDOT | E | + | X | $ Представления $ \ psi ^ \ ast (g) $ . Для обратного направления позвольте $ \ alpha $ Будьте некоторое назначение, удовлетворяющее $ (| V | + 1) \ CDOT | E |. + k $ Представления $ \ psi ^ \ ast (g) $ . Затем $ \ alpha $ должен представлять VC в G, как и в противном случае, количество удовлетворенных предложений в первой части $ \ PSI ^ \ AST (G) $ не более $ (| V | + 1) \ CDOT (| E | - 1)= | V | \ CDOT | E | + | Е | - | V | - 1 $ и как $ \ alpha $ может удовлетворить максимум $ | v | $ пункты во второй части, общее количество довольных положений будет максимально $$ (| V | + 1) \ CDOT (| E | - 1) + | V |= | V | \ CDOT | E | + | Е | - 1 <(| V | + 1) \ cdot | e | $$ Тем не менее, это подразумевает, что общее количество удовлетворенных предложений в первой части должно быть точно $ (| V | + 1) \ CDOT | E | $ и, таким образом, SPAN CLASS= «Математический контейнер»> $ K $ Представления второй части удовлетворены $ \ alpha $ , поэтому $ \ alpha $ соответствует vc $ x_ \ alpha $ размером $ K $ в $ g $ .

Обратите внимание, что для ясности я не указывал 3 $ -dnf формула. Однако, как все пункты в $ \ psi ^ \ ast (g) $ размером с большинства $ 2 $ Вы можете Jus

t Добавьте избыточные литералы к положениям, чтобы взорвать их до размера $ 3 $ , если это нужно.

Я не уверен, что это лучший способ сделать это, но он должен работать.Я опущел некоторые детали для краткости, пожалуйста, не стесняйтесь просить дополнительные разъяснения, если вам что-то не понятно :)