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

Cook, 1971, The complexity of theorem-proving procedures, 151 Gupta, 1988, Single facility scheduling with nonlinear processing times, Computers and Industrial Engineering, 14, 387, 10.1016/0360-8352(88)90041-1 Karp, 1972, Reducibility among combinatorial problems, 85 Kubiak, 1993, Completion time variance minimization on a single machine is difficult, Operations Research Letters, 14, 49, 10.1016/0167-6377(93)90019-D Papadimitriou, 1982