The Complexity of Optimization Problems
Krentel, Mark W.
We study computational complexity theory and define a class of optimization problems called OptP (Optimization Polynomial Time), and we show that TRAVELLING SALESPERSON, KNAPSACK and 0-1 INTEGER LINEAR PROGRAMMING are complete for OptP. OptP is a natural generalization of NP (Nondeterministic Polynomial Time), but while NP only considers problems at the level of their yes/no question, the value of an OptP function is the optimal value of the problem. This approach enables us to show a deeper level of structure in these problems than is possible in NP.
computer science; technical report
Previously Published As