Об алгоритмической сложности классической задачи надежности

Доказано, что при каждом фиксированном $k\geqslant 2$ задача вычисления надежности является NP-трудной даже в классе $k$-униформных бинарных систем, в которых каждый элемент содержится не более чем в четырех минимальных путях, а вероятность отказа каждого элемента равна 1/2. Доказано, что задачи вычисления надежности и коэффициентов полиномов надежности эффективно разрешимы в классе бинарных систем с регулярными (пороговыми) структурными функциями и с произвольными вероятностями отказов своих элементов. Библиогр. 13.