Компактное представление набора решений экземпляра SAT

Этот вопрос возник у меня в голове после прочтения вклада Андраса Саламона и Колина Маккуиллана в мой предыдущий вопрос « Подсчет решений формул Monotone-2CNF» .

РЕДАКТИРОВАТЬ 30- ^го марта 2011 г.
Добавлен вопрос № 2.

РЕДАКТИРОВАТЬ 29- ^го октября 2010 г.
Вопрос перефразирован после предложения Андра формализовать его с помощью понятия хорошего представления набора решений (я немного изменил его понятие).

Пусть - общая формула CNF с переменными. Пусть будет его решением. Ясно, чтоможет быть экспоненциальным в . Пусть$F$$n$$S$$|S|$$n$$R$быть представление $S$ . $R$ считается хорошим, если и только если следующие факты верны:

1. $R$ имеет полиномиальный размер по $n$ .
2. $R$ позволяет перечислять решения в $S$ с полиномиальной задержкой.
3. $R$ позволяет определить $|S|$за полиномиальное время (т.е. без перечисления всех решений).

Было бы здорово, если бы за полиномиальное время можно было построить такой $R$ для каждой формулы.

Вопросов:

1. Кто-нибудь когда-нибудь доказывал, что существует семейство формул, для которых такое хорошее представление не может существовать?
2. Кто-нибудь изучал связь между представлением и симметриями, представленными ? Интуитивно понятно, что симметрии должны помочь компактно представить поскольку они избегают явного представления подмножества решений когда фактически сводится к одному решению (т. Из каждого вы можете восстановить любой другой путем применения правильной симметрии, таким образом, каждый сам по себе является представителем всего )$S$$F$$S$$S' \subset S$$S'$$s_i \in S'$$s_j \in S'$$s_i \in S'$$S'$

Как указано (редакция 3), вопрос имеет простой ответ: нет.

Причина в том, что даже для строго ограниченного класса представлений, данных булевыми схемами с вентилями AND, OR и NOT, нетривиальные нижние оценки не известны. (Ясно, что схема, которая представляет , также будет неявно представлять , и легко перечислить решения путем изменения входов в схему.)$F$$S$

Для еще более ограниченных представлений, таких как монотонные схемы или схемы с постоянной глубиной, известны экспоненциальные нижние границы. Существуют также экспоненциальные нижние границы для представления формул в форме CNF или DNF, хотя их можно рассматривать как частные случаи контуров с постоянной глубиной. Наконец, представления BDD можно рассматривать как компактные формы DNF, но существуют формулы, для которых BDD требует экспоненциального размера для любого переменного порядка.

Чтобы сделать ваш вопрос более точным, рассмотрите ответ @ Joshua более подробно и уточните, что вы подразумеваете под «тривиальным перечислением каждого решения».

Для версии 4 обратите внимание на утверждение о размере BDD. Часть того, что вы, похоже, спрашиваете: есть ли более компактное представление формул DNF, чем BDD? Пусть «BDD имеет суперполиномиальный размер» означает «каждый BDD, представляющий ту же функцию, что и , независимо от упорядочения переменных, имеет суперполиномиальный размер», а «хорошее представление» означает «представление, которое позволяет перечислять решения с полиномиальной задержкой». Этот более конкретный вопрос становится:$B$$B$

Есть ли семейство формул и хорошее представление, которое имеет полиномиальный размер, в то время как его BDD имеют суперполиномиальный размер?

Это отражает суть того, что вы спрашиваете?

[Этот ответ был в ответ на версию, предшествующую редакции 6 от 29 октября 2010 г.]

Я думаю, что вопрос более или менее работает сейчас, но осталась техническая проблема. А именно, как формализовать «тривиально перечислять каждое решение, просто глядя на такую ​​структуру». Возможно, наивная формализация (но единственная, которую я мог придумать на данный момент) такова: пусть обозначает представление множества решений из . На данный момент я не накладываю на никаких ограничений, кроме этого где - CNF от переменных. Тогда мы хотим, чтобы существовал алгоритм такой, что и$R(\varphi)$$S(\varphi)$$\varphi$$R$$|R(\varphi)| \leq poly(n)$$\varphi$$n$$A$$A(R(\varphi)) = S(\varphi)$$A$на входе выполняется за время .$R(\varphi))$$poly(n, |S|)$

При этой формализации единственными трудными случаями являются случаи, когда суперполиномиальная, но субэкспоненциальная. Остальные случаи обрабатываются следующим представлением и алгоритмом : if , тогда пусть . Если тогда пусть . просто выводит , а просто вычисляет грубой силой из . Поскольку в последнем случае это все еще выполняется за время .$S$$R$$A$$|S| \leq poly(n)$$R(\varphi) = (0, S)$$|S| \geq 2^{\Omega(n)}$$R(\varphi) = (1, \varphi)$$A(0, S)$$S$$A(1, \varphi)$$S$$\varphi$$|S| = 2^{\Omega(n)}$$O(|S|)$

Однако сложные случаи вообще невозможны при этой формализации. Если бы такие и существовали, это означало бы, что колмогоровская сложность -времени каждой была ограничена , что абсурдно (поскольку почти все множества имеют максимальную колмогоровскую временную сложность, а именно ). (Здесь - время работы как функция от .)$R$$A$$p$$S$$poly(n)$$S$$p$$|S|$$p$$A$$|S|$

(Обратите внимание, что если мы дополнительно требуем, чтобы выполнялся во времени , то в общем случае ответ на вопрос «нет», при условии, что : если имеет единственное решение, то решит и запустит время .$R$$poly(n, |\varphi|)$$P \neq PromiseUP$$\varphi$$A(R(\varphi))$$\varphi$$poly(n)$