An approach to estimating the complexity of probabilistic procedures for the postoptimality analysis of discrete optimization problems

It is shown that ZPP- and RP-probabilistic polynomial postoptimality analysis procedures for finding an optimal solution of a set cover problem that differs from the original problem in one position of the constraints matrix do not exist if an optimal solution of the original problem is known and if ZPP ?? NP (RP ?? NP). A similar result holds for the knapsack problem.