42
правки
Изменения
Нет описания правки
{{Теорема
|statement= Задача вычисления гиперобъема принадлежит классу #P трудных задач
|proof= Суть доказательства состоит в сведении задачи #MON-CNF к задаче вычисления значения гиперобъема. Так как доказано{{статья |автор = Karl Bringmann, Tobias Friedrich |заглавие = Approximating the volume of unions and intersections of high-dimensional geometric objects |ссылка = http://www.tex.uniyar.ac.ru/doc/shulmeis.pdf |место = ISAAC'2008 |год = 2008}}</ref><ref>, что #MON-CNF является #P-трудной, то это докажет теорему.
Задача MON-CNF состоит в нахождении количества удовлетворяющих подстановок для
<tex>f = \bigwedge \limits _{k=1}^n \bigvee_{i \in C_k} x_i</tex>
Таким образом произвели сведение, в значит задача вычисления гиперобъема принадлежит #P
}}
= Источники =
http://www.mpi-inf.mpg.de/~kbringma/paper/2008ISAAC_Volume.pdf
