Computational complexity analysis of discrete optimization problems with hard computable objective functionals

A new approach for proving the NP-hardness of discrete optimization problems is proposed. The approach is illustrated by a scheduling problem for parallel machines and identical jobs with processing times dependent, in particular of the machine state at the moment when the machine starts the job processing. The main obstacle in the NP-hardness proof of this problem is the absence of a possibility to use the standard scheme for proving the NP-hardness of discrete optimization problems. The proposed approach may be also used for the complexity analysis of ‘usual’ problems.