Состояние ПП-полноты MAJ3SAT

10

КРАТКИЙ ВОПРОС: Является ли MAJ-3CNF PP-полной проблемой при сокращении многие-один?

ДОПОЛНИТЕЛЬНАЯ ВЕРСИЯ: Общеизвестно, что MAJSAT (решающий, удовлетворяет ли большинство назначений пропозиционального предложения) PP-завершено при сокращениях много-один, а #SAT # P-завершено при сокращениях. Также очевидно, что # 3CNF (то есть #SAT, ограниченный формулами 3-CNF) является # P-полным, поскольку сокращение Кука-Левина экономно и дает 3-CNF (это сокращение фактически используется в книге Пападимитриу для покажите # P-полноту #SAT).

Похоже, что аналогичный аргумент должен доказать, что MAJ-3CNF является PP-полным при сокращениях много-один (MAJ-kCNF - это MAJSAT, ограниченный формулами kCNF; то есть каждое предложение имеет k литералов).

Тем не менее, в презентации Бэйли, Далмау и Колайтиса «Фазовые переходы ПП-полных проблем удовлетворенности» авторы отмечают, что «MAJ3SAT, как известно, не является ПП-полным» (презентация на https: //users.soe.ucsc .edu / ~ kolaitis / talk / ppphase4.ppt ). Это предложение, по-видимому, не фигурирует в их соответствующих документах, только в их презентациях.

Вопросы: Может ли доказательство того, что # 3CNF является # P-полным, действительно быть адаптировано для доказательства того, что MAJ3CNF является PP-полным? Учитывая заявление Бэйли и др., Кажется, нет; если доказательство не содержит, то: Есть ли доказательство того, что MAJ-3CNF является PP-полным? Если нет, есть ли какая-то интуиция относительно разницы между PP и #P в отношении этого результата?

Фабио Козман
источник
4
Типичное сокращение от CircuitSAT до 3sat не работает, потому что оно вводит много новых переменных. Таким образом, хотя у вас может быть 2 ^ (n-1) +1 удовлетворяющих назначений для данной схемы с n входами, и у вас будет это много для экземпляра 3sat, число переменных в экземпляре 3cnf намного больше, чем n, так что это число больше не является «большинством удовлетворяющих заданий». Обратите внимание, что Maj-3sat по-прежнему сложен как минимум NP, потому что вы можете добавить много фиктивных удовлетворяющих заданий.
Райан Уильямс
@RyanWilliams Как насчет того, чтобы мы взяли этот экземпляр 3CNF, отрицали его и получили экземпляр 3DNF (отрицание занимает много времени, а когда вы отрицаете выражение CNF, вы получаете выражение DNF). Тогда исходный экземпляр CNF имел более (2 ^ (n-1)), удовлетворяющих назначениям истинности, если и только если экземпляр 3DNF имеет более (2 ^ ((n + K) -1), удовлетворяющих назначениям истинности, где K - это количество дополнительных переменных ...
Tayfun Pay
Преобразование cnf в dnf вообще не требует много времени. Быстрая проверка работоспособности: если это было сделано, то P = NP ... более сложная проверка: есть cnfs из poly (n) предложений, минимальный эквивалентный dnfs которых имеет много выражений exp. См. Например scholar.google.com/…
Райан Уильямс
@RyanWilliams 1) Требуется много времени, чтобы отрицать логическое выражение. 2) Когда вы отрицаете CNF, вы получаете DNF, и наоборот. Самое главное, отрицание CNF за полиномиальное время и получение взамен DNF не меняет сложности этой проблемы. Вам нужно будет найти ложное назначение истины для отрицательной формулы CNF, которая теперь является формулой DNF. Это NP-Complete, чтобы найти фальсифицирующее правдивое назначение для формулы DNF ...
Tayfun Pay
@RyanWilliams Я знаю работы, которые вы цитировали. Однако вы получаете выражение DNF, когда отрицаете выражение CNF. И это занимает полиномиальное время по отношению к длине ввода.
Tayfun Pay

Ответы:

1

SHORT ОТВЕТ:
Это неизвестно , будет ли является -полной проблемы при многих-один сокращениях.P PMAJ3CNFPP


ПОЛНЫЙ ОТВЕТ:
Прежде всего, вы обращаетесь к Бэйли, Далмау и Колайтису и их работе над «PP Фазовыми переходами -полных проблем удовлетворенности» в вашем вопросе. Позвольте мне процитировать их:

'Стоит также отметить, что, хотя является -полным, неизвестно, существует ли целое число , такое что is -complete. 'P P k 3 M A J O R I T Y K S A T P PMAJORITY SATPPk3MAJORITY kSATPP

[ http://www.sciencedirect.com/science/article/pii/S0166218X06004665 ]

Это действительно правильно, что сокращение Кука-Левина является экономным и производит 3CNF из данного CNF. Поскольку является -полным, из этого сразу следует, что также является -полным при экономном сокращении. Однако, как уже указывалось в комментарии, экономные сокращения не сохраняют большинство. Эти сокращения вводят вспомогательные переменные, чтобы уменьшить размер предложений, но, в свою очередь, эти вспомогательные переменные увеличивают общее количество назначений. Например, рассмотрим 4CNF, который состоит из одного предложения:# P # 3 C N F # P#CNF#P#3CNF#P

ϕ=(x1x2x3x4)

который превращается в

ϕ=(x1x2y)(y(x3x4))

используя вспомогательную переменную и, наконец, 3CNFy

ψ=(x1x2y)(¬yx3x4)(y¬x3)(y¬x4).

Это преобразование четко сохраняет количество моделей, но легко видеть, что большинство не сохраняется. имеет 15 удовлетворяющих назначений из 16 назначений, тогда как имеет 15 удовлетворяющих назначений из 32 назначений. В первом случае удовлетворенность большинства сохраняется, тогда как во втором удовлетворенность большинства не выполняется.ϕψ

Следовательно, НЕТ, доказательство того, что # 3CNF является -полным, нельзя адаптировать для доказательства того, что является -полным? Остается открытым ли является -полной проблемы при многих-один сокращениях.#PMAJ3CNFPPMAJ3CNFPP

# P P P # 3 C N F D # 3 C N F ϕ m 0 ϕ m D # 3 C N F D # 3 C N F P P M A J 3 C N F D # 3 C N FMAJ3CNF не дает большого понимания различия между и . На самом деле вариант принятия решения , скажем, , определяется следующим образом: учитывая CNF и число , решите, имеет ли хотя бы удовлетворяющих задания. Обратите внимание, что для нас не волнует большинство. Таким образом, мы можем преобразовать любой CNF в 3CNF, используя экономное сокращение, которое доказывает, что является -полным при сокращении многие-один.#PPP#3CNFD#3CNFϕm0ϕmD#3CNFD#3CNFPPMAJ3CNF - это просто другая проблема, чем .D#3CNF

Эй Эй Эй
источник
3SATP3SAT