Paper
The Complexity of the Postoptimality Analysis Procedures for ZPP Class
- Authors:
- Victor A. Mikhailyuk
- Abstract
- It is shown that a ZPP-probabilistic polynomial postoptimality analysis procedures to calculate optimal solution of set covering problem that differs from original problem in one position of matrix of constraints do not exist on condition that the optimal solution to the original problem is known and unless ZPP=NP. Similar result takes place for the knapsack problem.
- Keywords
- Postoptimality Analysis; Probabilistic Turing Machine; ZPP-probabilistic Polynomial Postoptimality Analysis Procedures
- StartPage
- 59
- EndPage
- 62
- Doi