42
правки
Изменения
Нет описания правки
|statement= Задача вычисления гиперобъема принадлежит классу #P трудных задач
|proof= Суть доказательства состоит в сведении задачи #MON-CNF к задаче вычисления значения гиперобъема. Так как доказано
<ref>{{статья
|автор = Karl Bringmann, Tobias Friedrich
|заглавие = Approximating the volume of unions and intersections of high-dimensional geometric objects
|место = ISAAC'2008
|год = 2008
}}</ref><ref>
, что #MON-CNF является #P-трудной, то это докажет теорему.
Задача MON-CNF состоит в нахождении количества удовлетворяющих подстановок для
}}
= Источники = Примечания ==http://www.mpi-inf.mpg.de/~kbringma/paper<references /2008ISAAC_Volume.pdf>
