COMPLEXITY OF A CLASS OF NONLINEAR COMBINATORIAL PROBLEMS RELATED TO THEIR LINEAR COUNTERPARTS

The ultimate purpose of our analysis is to show that for any class of linear combinatorial problems assumed to be NP-hard, the class of thei r strictly nonlinear counterparts is also NP-hard. In this paper, we s et the framework, and prove the result for a class of linear integer p rogramming problems with bounded feasible sets and their nonlinear cou nterparts. We also discuss briefly the complications that may arise wh en the feasible set is unbounded, and as a result some strictly nonlin ear problems become easy even though their linear versions are hard.