Вычислительная сложность алгоритмов локального апостериорного вывода в алгебраических байесовских сетях

В статье рассматривается локальный апостериорный вывод в алгебраических байесовских сетях. Для трёх видов свидетельств (детерминированного, стохастического и неточного) описывается способ проведения вывода и доказываются оценки сложности предлагаемых вычислений. В случае, когда вывод сводится к решению задач линейного программирования, оценка сложности даётся в виде числа таких задач, а так же оценки числа переменных и ограничений в них. В остальных случаях сложность описывается в числе арифметических операций.