Как доказать, что ограниченная версия 3SAT, в которой букваль не может возникнуть более одного раза, может быть разрешена в полиномиальное время?

Question

Я пытаюсь выполнить задание (взято из книги Алгоритмы - С. Дасгупта, Ч. Пападимитриу и УФ -Вазирани, Глава 8, задача 8.6A), и я перефразирую то, что он утверждает:

Учитывая, что 3SAT остается NP-полным, даже если это ограничивается формулами, в которых каждый буквал появляется не более дважды, покажите, что если каждый буквальный буква не появляется не более одного раза, то проблема решается в полиномиальное время.

Я попытался решить это, разделяя положения на несколько групп:

1. Положения, которые не имели никакой переменной общей с остальными пунктами
2. Положения, которые имели только 1 общую
3. Положения, которые имели 2 общих
4. Положения, в которых имели все общие

Мои рассуждения были предприняты в соответствии с тем, что # # таких групп является конечным (из -за навязанного ограничения литерала, присутствующего более одного раза), и мы могли бы сначала попытаться удовлетворить наиболее ограниченную группу (группа 4), а затем заменить первое место привести к меньшим ограниченным группам (3, 2, а затем 1), но я понял, что это никуда не приводит меня, так как это не сильно отличается от случая для ограниченной версии 3SAT, в которой может появиться каждый буквальный больше всего дважды, что было доказано, что является NP-полным.

Я пытался искать в Интернете любые подсказки/решения, но все, что я мог получить, это было эта ссылка, в котором указанный намек не имел достаточного смысла для меня, что я воспроизводит дословно здесь:

Подсказка: Поскольку каждый буквал появляется не более одного раза, преобразовать эту проблему в проблему 2SAT - следовательно, полиномиальное время, если буквальный $ x_i $ появляется в пункте $ C_J $ и дополнение $ x_i $ (то есть $ overline {x_i} $) В пункте $ c_k $, постройте новое пункт пункта $ c_j lor overline {c_k} $.

Оба $ C_J $, так и $ C_K $ имеют по три литерала в каждом - я не понял, как мне следует преобразовать его в 2SAT, выполнив $ C_J Lor Overline {C_K} $ (или $ Overline {C_J LOR C_K} $, если я прочитаю это неправильно).

Любая помощь в расшифровке намека, либо предоставление пути, который я могу исследовать, будет очень оценена.

Answer 1

Без потери общности мы можем предположить, что каждая переменная появляется точно один раз положительно и точно один раз отрицательно (если переменная появляется только после того, как установит свое значение для удовлетворения пункта и удаления пункта). Мы также можем предположить, что переменная не появляется в пункте более одного раза (если переменная появляется как положительно, так и отрицательно в пункте, то пункт выполняется и может быть удален). Это не изменит удовлетворенность.

Теперь используйте правило разрешения Чтобы устранить переменные один за другим (поскольку каждая переменная появляется точно так же положительно, и один раз отрицательно это детерминированный процесс). Если в какой -либо момент мы получаем пустое предложение, набор предложений является неудовлетворительным, в противном случае он удовлетворен. Это потому что:

• Разрешение является полной системой пропозиционального доказательства (т. Е. Если пункт логически подразумевается набором предложений, то он можно получить из набора предложений, используя только правило разрешения),

• Набор предложений является неудовлетворительным, если он логически подразумевает пустое предложение.

Этот алгоритм займет полиномиальное время, так как каждая переменная разрешена ровно один раз. В частности, каждое применение разрешения уменьшит общее количество предложений одним, поэтому количество предложений не увеличивается. Например, применение разрешения к $ (x lor b) land ( overline {x} lor c) land dots) $ wields $ (b lor c) land dots $, что имеет на одну меньше пункта чем до разрешения. Напротив, если вы применили это к формуле 3SAT без ограничения на количество появлений каждого буквального, применение разрешения может привести к увеличению количества пунктов в геометрической прогрессии.