КРАТКИЙ ВОПРОС: Является ли 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 в отношении этого результата?
источник
Ответы:
SHORT ОТВЕТ:MAJ3CNF PP
Это неизвестно , будет ли является -полной проблемы при многих-один сокращениях.P P
ПОЛНЫЙ ОТВЕТ:PP Фазовыми переходами -полных проблем удовлетворенности» в вашем вопросе. Позвольте мне процитировать их:
Прежде всего, вы обращаетесь к Бэйли, Далмау и Колайтису и их работе над «
'Стоит также отметить, что, хотя является -полным, неизвестно, существует ли целое число , такое что is -complete. 'P P k ≥ 3 M A J O R I T Y K S A T P PMAJORITY SAT PP k≥3 MAJORITY kSAT PP
[ http://www.sciencedirect.com/science/article/pii/S0166218X06004665 ]
Это действительно правильно, что сокращение Кука-Левина является экономным и производит 3CNF из данного CNF. Поскольку является -полным, из этого сразу следует, что также является -полным при экономном сокращении. Однако, как уже указывалось в комментарии, экономные сокращения не сохраняют большинство. Эти сокращения вводят вспомогательные переменные, чтобы уменьшить размер предложений, но, в свою очередь, эти вспомогательные переменные увеличивают общее количество назначений. Например, рассмотрим 4CNF, который состоит из одного предложения:# P # 3 C N F # P#CNF #P #3CNF #P
который превращается в
используя вспомогательную переменную и, наконец, 3CNFy
Это преобразование четко сохраняет количество моделей, но легко видеть, что большинство не сохраняется. имеет 15 удовлетворяющих назначений из 16 назначений, тогда как имеет 15 удовлетворяющих назначений из 32 назначений. В первом случае удовлетворенность большинства сохраняется, тогда как во втором удовлетворенность большинства не выполняется.ϕ ψ
Следовательно, НЕТ, доказательство того, что # 3CNF является -полным, нельзя адаптировать для доказательства того, что является -полным? Остается открытым ли является -полной проблемы при многих-один сокращениях.#P MAJ3CNF PP MAJ3CNF PP
# 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, используя экономное сокращение, которое доказывает, что является -полным при сокращении многие-один.#P PP #3CNF D#3CNF ϕ m≥0 ϕ m D#3CNF D#3CNF PP MAJ3CNF - это просто другая проблема, чем .D#3CNF
источник