An approach to estimating the average-case complexity of postoptimality analysis of discrete optimization problems

It is shown that an algorithm polynomial on average with respect to μ and that determines an optimal solution to a set cover problem that differs from the initial problem in one position of the constraint matrix does not exist if the optimal solution of the original problem is known and DistNP is not a subset of Average-P. A similar result takes place for the knapsack problem.