Михайлюк В. А.
Подход к оценке сложности в среднем постоптимального анализа дискретных задач оптимизации

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

It is shown that an algorithm polynomial on the average with respect to to calculate the optimal solution of the set cover problem that differs from the original problem in one position of the constraint matrix doesn't exist if the optimal solution of the original problem is known and unless DistNP <$E symbol <173>> Average-P. A similar result is true for the knapsack problem.

PDF