A very difficult scheduling problem with communication delays

A set of unit-time tasks has to be processed on an unrestricted number of processors subject to precedence constraints and unit-time communication delays such that the makespan is minimized. What is the smallest number m* such that increasing the number of processors beyond m* cannot decrease the makespan any more? We prove that answering this problem is complete for the complexity class . Hence, the problem is at least as difficult as all the problems in and at least as difficult as all the problems in , and unless some complexity classes collapse, it is even more difficult than all these problems. This answers a question raised by Ivan Rival.