Complexity of a class of nonlinear combinatorial problems related to their linear counterparts

The ultimate purpose of the present analysis is to show that for any class of linear combinatorial problems assumed to be NP-hard, the class of their strictly nonlinear counterparts is also NP-hard. In this paper, the authors set the framework, and prove the result for a class of linear programming problems with bounded feasible sets and their nonlinear counterparts. They also discuss briefly the complications that may arise when the feasible set is unbounded, and as a result some strictly nonlinear problems become easy even though their linear versions are hard.