Сложность вероятностных процедур анализа устойчивости целочисленных задач булева программирования

Abstract

Показано, що для задач про покриття (які відрізняються однією позицією матриці обмежень) не існує поліноміальних k-ймовірнісних процедур аналізу стійкості (k∊{ZPP, RP}) при k≠ NP.It is shown that the set covering problems (which differ in one position of the constraint matrix) have no -probabilistic polynomial procedures for sensitivity analysis (k∊{ZPP, RP}) if k≠ NP.