2005 | OriginalPaper | Buchkapitel
An Alternative Proof That Exact Inference Problem in Bayesian Belief Networks Is NP-Hard
verfasst von : Mustafa Tacettin, Tonguç Ünlüyurt
Erschienen in: Computer and Information Sciences - ISCIS 2005
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Exact inference problem in belief networks has been well studied in the literature and has various application areas. It is known that this problem and its approximation version are NP-hard. In this study, an alternative polynomial time transformation is provided from the well-known vertex cover problem. This new transformation may lead to new insights and polynomially solvable classes of the exact inference problem in Bayesian belief networks.