Изменения

Перейти к: навигация, поиск

Оценка сложности вычисления гиперобъема

2 байта добавлено, 16:48, 19 июня 2012
Нет описания правки
<tex>\iff \forall i : x_i = 1 \to a^k_i = 2 \iff \forall i : x_i = 1 \to i \notin C_k \iff (x_1,...,x_d) </tex> удовлетворяет <tex>\bigwedge_{i \in C_k} \neg x_i</tex> для некоторого <tex>k \iff (x_1,...,x_d)</tex> удовлетворяет <tex>\overline{f}</tex>
Заметим, что так как <tex>\mu (B_{x_1,...,x_d}) = 1 \to \mu (\bigcup \limits _{k=1}^n) A_k = |\{(x_1,...,x_d) \in \{0,1\}^d| (x_1,...,x_d)</tex> удовлетворяет <tex>\overline{f}\}|</tex>
Таким образом произвели сведение, в значит задача вычисления гиперобъема принадлежит #P
42
правки

Навигация