I'll try to be as abstract as possible, but where needed, I'll give some concrete examples. If you have any questions, please ask. Note, I'm doing this for my hobby, not for any sort of homework. I've only followed an introductory course on computational complexity, so I'll let that be my excuse if I sound absolutely vague. ;) The problem originated in a game that I frequently play and it's a problem I want to solve or of which I want to least approximate the optimum solution. Background First, some background about the problem at hand. This part will be relatively concrete so I can sketch You might know about the Guitar Hero series of video games. If you don't, here's a short description: Players, using plastic imitation instruments, play songs. The more notes you play flawless, the bigger your final score. While the first games limited you to bass and guitar, the latest game allows any four-player combination of instruments (vocals, bass, drums and guitar). You can have three vocalists and a single drummer, or a more conventional one of each band. For every ten notes you play, your multiplier goes up by one, up to a maximum of four. When using Star Power, an in-game element, your current multiplier doubles, effectively doubling the score you're getting per note for a short period of time. After it fades, everything is back to normal. There are limitations to activating Star Power and there's a limit to how much you can obtain. Activating Star Power is called a Star Power Activation (or simply an Activation), and a group of activations is called a Star Power Path (or simply a Path). Star Power can be achieved by playing certain groups of notes (Star Power Phrases) flawlessly and the amount you get is variable for guitars, depending on the presence of sustained notes. There's some music theory behind Star Power with which I won't bore you. No song lasts eternally and as a logical consequence, there's a limit on your score. That limit can only be reached by applying Star Power at the correct time. That is what this problem is all about. The problem In concrete terms, the problem can be stated as follows for each and every song: "What is the path that results in the highest possible score for every combination of instruments?". Clearly, this is an optimization problem. The more instruments, the harder it gets, but the essence is of the problem is the same. For this problem, we can assume that the player plays perfectly. I'm not asking you to solve it! I'm interested in proving to which complexity class it does(n't) belong. My initial idea My theory is that this problem is in NP and that it is a form of a job scheduling problem. I'm guessing that it's in NP because brute-forcing it for a single instrument would take quite some time given all of the points during which Star Power can be activated, let alone for four instruments! When you look at the song from an abstract point of view, it's simply a time line with a starting point at beat 1 with the last beat being beat x. Star Power Phrases can abstractly be seen as pre-scheduled, static jobs with a variable bonus, but never a penalty. We'll call these Phrase Jobs. Star Power Activations can abstractly be seen as the jobs which need to be scheduled. These jobs have a dependency on the Phrases being executed succesfully. These jobs have a variable bonus, too and just like the Phrases, no penalty. The bonus is simply the number points that are accumulated during the Activation. We'll call these Activation Jobs. The duration of the Activation Jobs is variable and entirely dependent on the bonus of the Star Power Phrases and dependent on some things based on music theory. Depending on the game you're playing, Activation Jobs disable Phrase Jobs. In other words: If an Activation Job is being executed on and you encounter a Phrase Job, the job simply doesn't exist and will not net you Star Power. In more abstract terms: The two jobs cannot be executed parallel. In other games, this doesn't happen and Activation Jobs do not disable Phrase Jobs. In more abstract terms: The two jobs can most definitely run parallel and the completion of Phrase Job will directly influence the ongoing Activation Job upon completion. The optimal solution is the path where the bonus of the Activations is the highest, thus resulting in the highest possible score. I'm not entirely sure how to proceed with proving the complexity of this problem. Obviously, it needs to be abstracted a bit more because even now, in its abridged version, it is still connected to the game, let alone when I add music theory on how Star Power and point calculation works. As I said, I've only done an introductory course on this subject and class complexity was only briefly mentioned, so I only know the prerequisites to what makes a problem NP, NP-C or NP-H but I'm in no way capable of proving to which complexity class it belongs and my mathematical knowledge is not sufficient to figure it out on my own. Any and all help is greatly appreciated. If there's anything you need to know, just ask and my apologies if this is in the wrong forum.