Уникальные SAT против ровно

12

Уникальная SAT является хорошо известной проблемой: учитывая формулу CNF , верно ли, что F имеет ровно одну модель?FF

Меня интересует проблема «точно -SAT»: учитывая формулу CNF F и целое число m > 1 , правда ли, что F имеет ровно m моделей?mFm>1Fm

Обе проблемы выглядят одинаково. Итак, мои вопросы:

1- Приводит ли Polytime «точно -SAT» (много-один или Тьюринг) к уникальному SAT?m

2- Знаете ли вы какие-либо ссылки на эту тему?

Спасибо за ваши ответы.

Приложение , первые статьи о сложности Exactly SAT:m

1- Янош Симон, «О разнице между одним и многими», в трудах четвертого коллоквиума по автоматам, языкам и программированию, 480–491, 1977.

2. Клаус В. Вагнер. Сложность комбинаторных задач с кратким входным представлением, Acta Informatica, 23, 325-356, 1986.

В обеих статьях показано , что точно SAT ( m 1 ) является C = полной (при сокращениях много-один), где класс C относится к Иерархии подсчета (CH) классов сложности. Неформально C содержит все проблемы, которые можно выразить как решение о том, имеет ли данный экземпляр хотя бы m много полиномиальных размерных доказательств (известно, что класс C совпадает с классом P P ). Класс C = является вариантом C , где «ровно m » заменяет «не менее m ».mm1C=CCmCPPC=Cmm

Ксавье Лабуз
источник
4
Это сводится к разложению по Тьюрингу: найдите решение, добавьте предложение, исключая его, и повторяйте, пока формула не станет неудовлетворительной.
Каве
1
1. машина сообщит количество решений или о том, что у нее более решений. 2. Вы можете добавить отрицание соединения, описывающее решение. m
Каве
1
Если вы не знаете связь между PP и подсчетом количества решений, пожалуйста, ознакомьтесь с учебником по теории сложности, таким как Papadimitriou.
Цуёси Ито
6
(1) Если m ограничено полиномиально, ваша задача сводится к многозначному времени многозначного времени, сводящемуся к Unique SAT, путем обработки списка из m решений, отсортированных в лексикографическом порядке, как одного сертификата. (2) Пожалуйста, не принимайте мой ответ как доказательство того, что вы задали свой вопрос в нужном месте. Я думаю, что этот конкретный вопрос находится на границе между темой и темой. Вы должны подумать о том, чтобы задать свои будущие вопросы где-нибудь еще.
Tsuyoshi Ito
4
Хотя вы утверждаете, что m ограничено полиномиально, некоторые из утверждений в вопросе требуют, чтобы m было произвольным и больше не выполняются, если вы ограничиваете m, чтобы быть ограниченным полиномом. Вы должны понять, о чем говорите, прежде чем сможете задать связный вопрос. Вот почему я не хочу публиковать ответ на этот вопрос здесь, где вопросы должны быть на уровне исследований.
Tsuyoshi Ito

Ответы:

13

m

m

Ноам
источник
mnmmm=2O(n)mm
Большие m все еще не ставят проблему в P. Сообщение об обновлении неверно, поскольку утверждение, что именно-k-sat является C = P-complete, верно, когда k является частью ввода, и, таким образом, ваше сокращение до k / 2 Сат не имеет смысла.
Ноам
mmy1,y2ymF=Fy1y2ymFFmFF
FFm|F|