42
правки
Изменения
Нет описания правки
|proof= Суть доказательства состоит в сведении задачи #MON-CNF к задаче вычисления значения гиперобъема. Так как доказано
<ref>
Roth D. Roth. , On the hardness of approximate reasoning. , Artif. Intell., 82: 273–302, 1996, http://cogcomp.cs.illinois.edu/papers/hardJ.pdf
</ref>
, что #MON-CNF является #P-трудной, то это докажет теорему.
Приведем псевдокод алгоритма для аппроксимации гиперобъема объединения тел. В алгоритме, приведенном в
<ref>
</ref>
используются три оракула: PointQuery, VolumeQuery и SampleQuery, каждый из которых ошибается с вероятностью <tex>\epsilon_p, \epsilon_v</tex> и <tex>\epsilon_s</tex> соответственно.
