Рассчитать вероятность того, что один набор будет покрыт случайными подмножествами

Question

Предположим, что эти два набора заданы как input :

• Один набор U как вселенная
• И один набор S , содержащий некоторые из подмножеств U .

Членам S присваиваются случайные флаги 0 или 1. Для каждого члена S вероятность флага1 - p , а флаг 0 - (1-p) .

Требуемый вывод : Вероятность объединения флага1 подмножество в S = U '

Хотя рассмотрение всех возможных комбинаций подмножеств флага 1 в S является тривиальным алгоритмом, чтобы привестина выходе время выполнения этого метода грубой силы явно экспоненциально.

Существует ли какой-либо алгоритм с полиномиальным временем, который приводит к точному или приблизительному результату?Или мы можем свести проблему к любому известному, как set-cover?

Answer 1

Получить точный ответ # P-hard (считая аналог NP, то есть, по крайней мере, как сложный), поскольку эта проблема обобщает монотон 2-CNF-SAT, который известен как # P-hard (валлийский, Доминик;Гейл, Эми (2001), «Сложность подсчета проблем», Аспекты сложности: миникурсы по алгоритмике, сложности и вычислительной алгебре: математический семинар, Каикоура, 7–15 января 2000 г., с. 115ff, теорема 57.).Сокращение состоит в том, чтобы установить U в набор идентификаторов предложений и позволить каждому подмножеству в S быть набором предложений, в которых появляется некоторая переменная.РЕДАКТИРОВАТЬ: установить p = 1/2 для каждого набора, естественно.