Том 5, серия 1, номер 4, 1998 г., Стр. 71-80

УДК 519.71+519.1
А. А. Черняк
Об алгоритмической сложности классической задачи надежности

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

Черняк А. А. ¹
1. Белорусский государственный университет, мех.-мат. факультет,
пр. Фр. Скорины, 4, 220050 Минск, Беларусь

Статья поступила 4 июня 1997 г.
Исправленный вариант — 18 февраля 1998 г.