Determination of the Entropy of a Belief Network is NP-Hard

Citation: Gregory F. Cooper and Edward Herskovits. (1991) Determination of the Entropy of a Belief Network is NP-Hard. In KSL-90-21, June,1991.

Publication techreport ( Edit )
type	Technical Report
bibtype	techreport
Bibtex basics
author	Gregory F. Cooper and Edward Herskovits
title	Determination of the Entropy of a Belief Network is NP-Hard
number	KSL-90-21
institution	Knowledge Systems, AI Laboratory
address	Stanford, CA, USA
year	1991
month	June
Bibtex more
Access Paper
abstract	In this paper, we analyze the computational complexity of determining the entropy of an arbitrary probability distribution represented by a belief network, and show that this task is NP-hard in the number of nodes in the network. This analysis is similar to the analysis of the computational complexity of inference using belief networks.

KSL Technical Report ID: KSL-90-21

Abstract	In this paper, we analyze the computationa … In this paper, we analyze the computational complexity of determining the entropy of an arbitrary probability distribution represented by a belief network, and show that this task is NP-hard in the number of nodes in the network. This analysis is similar to the analysis of the computational complexity of inference using belief networks. lexity of inference using belief networks.
Address	Stanford, CA, USA +
Author	Gregory F. Cooper and Edward Herskovits +
Bibtype	techreport +
Has author	Gregory F. Cooper and Edward Herskovits +
Has identifier	KSL-90-21 +
Has publishing details	June,1991 +
Has title	Determination of the Entropy of a Belief Network is NP-Hard +
Has where published	KSL-90-21 +
Has year	1991 +
Institution	Knowledge Systems, AI Laboratory +
Ksl tr id	KSL-90-21 +
Month	June +
Number	KSL-90-21 +
Process note	NO +
Title	Determination of the Entropy of a Belief Network is NP-Hard +
Year	1991 +