Простой случай SAT, который нелегок для разрешения дерева

10

Существует ли естественный класс формул CNF - предпочтительно тот, который ранее изучался в литературе - со следующими свойствами:C

  • является простым случаем SAT, как, например, Horn или 2-CNF, т. Е. Членство в C можно проверить за полиномиальное время, а формулы F C можно проверить на выполнимость за полиномиальное время.CCFC
  • Неудовлетворительные формулы как известно, не имеют коротких (полиномиального размера) древовидных опровержений разрешения. Еще лучше было бы: есть неудовлетворительные формулы в C, для которых известна суперполиномиальная нижняя оценка для древовидного разрешения.FCC
  • С другой стороны, неудовлетворительные формулы в как известно, имеют короткие доказательства в некоторой более сильной системе доказательств, например, в dag-подобном разрешении или в некоторой даже более сильной системе.C

не должно быть слишком редким, то есть, содержит множество формул с п переменными, для каждого (иликрайней мередля большинства значений) п N . Он также должен быть нетривиальным в том смысле, что он содержит как выполнимые, так и неудовлетворительные формулы.CnnN

Следующий подход к решению произвольной формулы CNF должен быть осмысленным: найти частичное назначение α st, остаточная формула F α находится в C , а затем применить алгоритм полиномиального времени для формул в C к F α . Поэтому я хотел бы получить другие ответы, помимо совершенно других ограничений из принятого в настоящее время ответа, так как я думаю, что редко, когда произвольная формула становится совершенно другим ограничением после применения ограничения.FαFαCCFα

Ян Йоханнсен
источник
1
Ян, я думаю, что все еще можно привести искусственные примеры, например, PHP union Horn. Я не уверен, как можно формально исключить такие примеры. Хотите какой-нибудь класс, который имеет имя и изучен? (PS: если вы объясните, почему вы ищете такой класс, который мог бы помочь с какими дополнительными требованиями класс должен удовлетворить.)
Kaveh
n+1n
@Kaveh, вы правы, но, вероятно, никогда нельзя исключать искусственные примеры. Я попытался уточнить вопрос немного.
Ян Йоханнсен
Желаемое условие в вашем последнем редактировании по существу требует наследственного класса. Обратите внимание, что прямое кодирование всех разных дает наследственный класс экземпляров SAT. Возможно, вы могли бы уточнить, почему основной пример, который мы имеем (как предложено тремя комментариями / ответами), не подходит?
Андрас Саламон
1
Я думаю, что Ян хочет естественный класс формул, а не семейство формул. Сложность как «естественная», так и «классная» - это неформальные понятия. Я предполагаю, что одно условие, которое можно поставить для того, чтобы быть классом, - это требовать некоторого уровня выразительности или замыкания, чтобы семейства формул, таких как PHP, не считались классом. И для естественности я думаю, что если урок был изучен ранее или имеет название, то он, вероятно, будет естественным.
Каве

Ответы:

10

Звучит так, как будто вас интересуют разные ограничения (и ваше последнее предложение на правильном пути). Это нетривиальные примеры принципа голубиного отверстия, когда число голубей не обязательно превышает количество отверстий, и, кроме того, некоторые голуби могут быть исключены из некоторых отверстий.

Все различные ограничения могут быть решены путем сопоставления за полиномиальное время низкого порядка.

Когда все различные ограничения выражаются (с использованием одного из нескольких кодировок) в качестве экземпляров SAT, тогда изучение предложений, основанное на конфликте, обычно быстро находит решение, если оно существует. Однако чистое разрешение для PHP должно создавать суперполиномиально большой набор предложений, чтобы показать, что экземпляр является неудовлетворительным. Эта оценка явно справедлива для этой более общей проблемы. С другой стороны, напомним, что кодирование Кука PHP допускает опровержения расширенного разрешения полиномиального размера .

  • С.А. Кук, Короткое доказательство принципа голубиного отверстия с использованием расширенного разрешения , SIGACT News 8 28–32, 1976. doi: 10.1145 / 1008335.1008338

Недавняя работа в этом направлении - глава 5 диссертации Серджи Оливы , которая легла в основу работы с Альберто Ацериасом в CCC 2013.

Я ожидаю, что вы знаете о классическом результате Кука, так что, возможно, вы хотели ограничить возможности системы доказательства в своем третьем условии?

Андраш Саламон
источник
Не уверен, что это то, что ищет Ян, когда он спрашивает специально для CNF.
Миколас
@Mikolas: не могли бы вы уточнить, что вас беспокоит?
Андрас Саламон
1
Я имел в виду, что если у меня есть какой-то результат по поводу разных ограничений, то не ясно, как этот результат переводится в CNF. Как я понимаю вопросы, Ян хотел, чтобы CNF были сложными для дерева, но легкими для чего-то другого (например, dag-res). Мне также не ясно, почему PHP будет примером для этого, потому что PHP также экспоненциально для dag-res. (Кстати, упомянутый тезис выглядит опрятно!)
Миколас
@mikolas, как я понимаю, вопрос, если удовлетворительные / неудовлетворительные экземпляры семейства могут быть распознаны за время P, но это трудно для разрешения дерева или DAG, это то, что ищется. сейчас я не уверен, что это указано в каких-либо статьях, но на самом деле (кто-нибудь знает больше?) экземпляры PHP sat / unsat могут быть распознаны за время P.
ВЗН
1

Я не уверен, почему нужно также использовать формулу sat, но есть несколько статей о разделении между Общими и Резолюцией дерева, например [1]. Мне кажется, что это то, что вы хотите.

[1] Бен-Сассон, Эли, Рассел Импальяццо и Ави Вигдерсон. «Почти оптимальное разделение древовидного и общего разрешения». Combinatorica 24,4 (2004): 585-603.

Миколас
источник
1
Мне хорошо известны эти различия между древовидным и дагоподобным разрешением, но это дает только одно семейство формул. Это именно тот искусственный пример, которого я пытался избежать.
Ян Йоханнсен
0

Возможно, вас заинтересуют формулы SAT с небольшой (логарифмической) «шириной полосы» или «шириной линии». Эти формулы рекурсивно разделяются таким образом, что граница связи между разделами мала, и, следовательно, для их решения может использоваться подход динамического программирования с использованием перечислений. Тема была популярна в девяностых. Однажды я подсчитал точное число гамильтоновых циклов в небольшом графе длины дерева, состоящем из 24 000 вершин, так что проблемы #P с малой шириной дерева также разрешимы. Bodlaender является основным ориентиром.

Даниэль Пехоушек
источник
Я думаю, что по крайней мере формулы постоянной ширины дерева имеют короткие древовидные опровержения разрешения. Поэтому я не думаю, что этот класс отвечает требованиям вопроса.
Ян Йоханнсен
-1

эта следующая статья кажется близкой к тому, что запрашивается в некоторых отношениях (если она не подходит, возможно, JJ может уточнить, почему). вопрос хочет исключить экземпляры PHP (pigeonhole), основанные на отсутствии обеих формул true / false, но (как указано в других ответах) PHP является одним из наиболее хорошо изученных генераторов падежей / экземпляров со стороны теории и имеет всегда был генератором для обеих выполнимых / неудовлетворительных формул, хотя выполнимые формулы менее подчеркнуты / изучены.

nmmnm>nmn

Другой подход заключается в том, чтобы пойти в более эмпирическом ракурсе и просто генерировать случайные случаи (предположительно, вокруг точки перехода, легко достигающей 50%), и фильтровать их в соответствии с указанными критериями. для этого потребуются реализации разрешения дерева / разрешения DAG или «более сильные системы».

ВЗН
источник
1
Здесь применяется тот же комментарий, что и к ответу @Mikolas.
Ян Йоханнсен
1
не понимаю ваш комментарий, нужно больше информации. Я следую за комментарием Миколаса: «Как я понимаю вопросы, Ян хотел, чтобы CNF были сложными для дерева, но легкими для чего-то другого (например, dag-res)». что вы подразумеваете под "это дает только одну семью формул"? Ваш вопрос требует семейства формул.
vzn
1
Нет, у меня вопрос о классе формул. Для меня разница в том, что эти семейства формул имеют не более одной формулы на число переменных, в то время как в собственном классе должно быть много формул для каждого числа переменных, среди тех, которые являются удовлетворительными и неудовлетворительными.
Ян Йоханнсен
Я уже объяснил в нескольких местах (см. Комментарий здесь и другие ответы и на вопрос), почему это не то, что я ищу !! В частности, прочитайте последний абзац вопроса!
Ян Йоханнсен