42
правки
Изменения
Нет описания правки
Утверждается, что точное вычисление значения гиперобъема <tex>S(X)</tex> множества из <tex>n</tex> точек <tex>d</tex>-мерного пространства является [http://en.wikipedia.org/wiki/Sharp-P #P-трудной задачей], однако допускает эффективную аппроксимацию, а именно может быть аппроксимировано за
*полином от количество количества параметров,
*полином от количества решений,
*полином от качества аппроксимации.
== #P-трудность задачи вычисления гиперобъема ==
{{Определение
|definition=задача #MON-CNF -- (Satisfability problem for monotone boolean formulas) — задача вычисления количества удовлетворяющих подстановок для монотонной булевой формулы, записанной в [[КНФ ]] <tex>f = \bigwedge \limits _{k=1}^n \bigvee_{i \in C_k} x_i</tex>где клозы все дизъюнкты <tex> C_k \subseteq {1,...,d}</tex>
}}
{{Теорема|statement= Задача вычисления гиперобъема принадлежит классу #P трудных задач|proof= Суть доказательства состоит в сведении задачи #MON-CNF к задаче вычисления значения гиперобъема. Так как доказано, что #MON-CNF является #P-труднойСведем ее к задаче вычисления гиперобъема, то это докажет теорему.
Задача MON-CNF состоит в нахождении количества удовлетворяющих подстановок для
<tex>f = \bigwedge \limits _{k=1}^n \bigvee_{i \in C_k} x_i</tex>
Количество ее удовлетворяющих подстановок равно <tex>2^d</tex> минус количество удовлетворяющих подстановок ее отрицания
<tex> \overline{f} = \bigvee \limits _{k=1}^n \bigwedge_{i \in C_k} \neg x_i</tex>
Таким образом произвели сведение, в значит задача вычисления гиперобъема принадлежит #P
}}
