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

Сеть с описанием взлома, приведенная на рис. 14.2, принадлежит к семейству сетей, в которых имеется самое большее один неориентированный путь между любыми двумя вершинами в сети. Такие сети называются односвязными (singly connected) сетями, или полидеревьями (polytree), и обладают одним особо привлекательным свойством: временная и пространственная сложность тонного вероятностного вывода в полидеревьях линейно зависят от размера сети. В данном случае размер определяется как количество элементов таблиц СРТ; если количество родительских вершин каждой вершины ограничено некоторой константой, то сложность также будет зависеть линейно от количества вершин. Эти результаты справедливы для любого упорядочения, совместимого с топологическим упорядочением сети.

Для многосвязных (multiply connected) сетей, подобных приведенной на рис. 14.9, а, процедура устранения переменной в наихудшем случае может иметь экспоненциальную временную и пространственную сложность, даже если количество родительских вершин в расчете на каждую вершину ограниченно. В этом нет ничего удивительного, если учесть, что вероятностный вывод в байесовских сетях является NP-трудным, поскольку включает вывод в пропозициональной логике как частный случай. Фактически можно показать (упр. 14.8), что эта задача является настолько трудной, насколько трудна задача вычисления количества выполняющих присваиваний для формулы пропозициональной логики. Это означает, что данная задача является #Р-трудной (читается "шарп-Р-трудной", или "диез-Р-трудной"), т.е. строго труднее, чем NP-полные задачи.

Существует тесная связь между сложностью вероятностного вывода в байесовской сети и сложностью задач удовлетворения ограничений (Constraint Satisfaction Problem — CSP). Как было показано в главе 5, трудность решения дискретной задачи CSP зависит от того, насколько "древовидным" является ее граф ограничений. Такие показатели, как ширина гипердерева, которые устанавливают пределы сложности решения задачи CSP, могут также применяться непосредственно к байесовским сетям. Более того, существует возможность обобщить алгоритм устранения переменной таким образом, чтобы он позволял находить решения не только в байесовских сетях, но и в задачах CSP.