The complexity of the cost-time tradeoff problem with non-convex functions

In this paper it is shown that the cost-time tradeoff problem with non-convex functions is NP-Hard. The proof is made by the conversion of a known NP-Hard problem in a particular instance of the cost-time tradeoff problem. Many authors have proposed non-polynomial algorithms to treat this problem without focusing its complexity. The proof here presented shows that, in fact, the existence of polynomial algorithms to deal with this problem is very unlikely.