Нижние границы на #SAT?

14

Проблема #SAT является канонической # P-полной проблемой. Это скорее функциональная проблема, чем проблема решения. При булевой формуле в пропозициональной логике спрашивается, сколько удовлетворяющих заданий имеет. Каковы лучшие нижние границы на #SAT?FF

Джорджио Камерани
источник

Ответы:

26

Насколько мне известно, никто не придумал, как использовать свойство «подсчета решений» #SAT в любой нижней границе детерминированных алгоритмов, поэтому, к сожалению, наиболее известные нижние оценки для #SAT в основном такие же, как и для SAT.

1/2ппО(N)

1/2Икс1/2Yпппп

Опрос на http://pages.cs.wisc.edu/~dieter/Papers/sat-lb-survey-fttcs.pdf дает обзор результатов в этом направлении.

Райан Уильямс
источник
Спасибо за ваш полезный ответ. Спасибо также за указатель на опрос.
Джорджио Камерани
6

Nпзнак равнорп

Мухаммед Аль-Туркистани
источник
1
Не могли бы вы предоставить ссылку?
MS Dousti
2
Интуитивно, FRPAS позволит вам различать случай нулевых решений и ненулевых решений, который является NP-полной задачей SAT.
Робин Котари
@SadeqDousti Ссылка - Дэвид Цукерман, О неприемлемых версиях NP-полных задач , SIAM Journal of Computing 25 (6): 1293-1304, 1996. Ссылки: DOI , домашняя страница автора . Фактически, он доказывает более сильный результат, что вы даже не можете приблизить логарифм числа решений, если NP = RP.
Дэвид Richerby
@DavidRicherby: я не ожидал получить ответ через 3 года! Большое спасибо: D
MS Dousti