To which complexity class does this optimization problem belong?

[Robbert]

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.

 

[timiox]

I have actually never studied complexity theory, so I know I can't answer your question. As far as the optimization goes, wouldn't you look for the portion of the song with the most notes available to get correct in the time period you are allotted for star power?

 

[Robbert]

I have actually never studied complexity theory, so I know I can't answer your question. As far as the optimization goes, wouldn't you look for the portion of the song with the most notes available to get correct in the time period you are allotted for star power?

Yes, basically.

Thing is, the amount of Star Power gathered is dependent on the number of beats, but only if there are sustained notes and if these have been manipulated by the tremolo arm. The amount received from phrases is always at least 25% of the total amount of Star Power you can have, but can be much more, up to 100%, if the tremolo arm is used on sustained notes.

The spending of it is dependent on the number of measures and the time signature. In general, it's pretty variable how long it lasts depending on those factors. You always need at least 50% of a full meter in order to activate.

An example on what I mean with a variable duration: Let's say you have 50% (which is good for four measures) of the meter and that we have two songs. The beats per minute of the songs is 120. One song has a constant time signature of 7/4 and the other of 4/4 (nevermind the technicality behind it).

The measures of the song in 7/4 time take longer than the measures of the song in 4/4 time, thus more time is spent in Star Power.
A short illustration: In 7/4 time, seven beats consist of a measure, so there are 120/7 measures in a minute, which is one per every 3,5 seconds.
In 4/4 time, there are four beats per measure = 120/4 = 30 measures per minute, one per every 2 seconds.
If the BPM of the 4/4 song is pretty low (60 or lower), then measures in 4/4 time will take longer than measures in 7/4 time at 120 bpm. 60/4 = 15 measures per minute, one per every four seconds.
In a song with mixed time signatures can be even more complex to plan Star Power.


Here is the simplest possible example I can think of to illustrate my point regarding paths: Let's say there are seven phrases in a song and none contain sustained notes. Thus, you need a minimum of two phrases before you can activate and you can collect a grand total of 7*25 = 175% of Star Power The song is always in 4/4 time at a constant BPM. There are several possibilities to distribute the SP:
- Obviously, a path of 2-2-2 will leave you with one unused phrase, which is a waste. But it's definitely possible get the maximum score witht his
- A 3-3 path uses all but one
- A 3-4 path uses all of them.
- A 2-2-3 path is possible, too
- Maybe 3-2-2 is the way to go
- What about 2-3-2?
- 4-3 is an idea. This is NOT the same as 3-4
- It may be an idea to do two two-phrase activations first, then gather another two, and activate before or during the last phrase, allowing you to extend your final activation immediately as soon as the phrase ends. You could denote this as 2-2-2(+1)
- 2(+1)-2-2
- 2-2(+1)-2


Those are only ten possible ways to do this in this simple situation with seven, simple phrases and there are a lot more possibilities than just this simply because activations can overlap accumulation. And this is only Star Power distribution itself.
Add to that, that the timing has to be just right in order to squeeze notes in for that optimum score. The optimum path correctly timed results in the highest possible score, but a poor timing (even if it's only off by a few beats) can make it the worst path ever. It's not always a matter of squeezing in as many notes as possible, sometimes it's a matter of using a poor and excellent activation in order to get the high score instead of two relatively good activations.

The number of possible paths grows even more when you factor in the fact that sustained notes can net you additional Star Power, sometimes allowing activation by hitting only a single phrase, thus adding extra activations. There are only very few songs which don't have sustained notes.

It gets even worse when you look at the time signatures I discussed earlier. In a song such as Them Bones, it is essential to time properly since the verses are in 7/4 time and the choruses in 4/4, yet it may not always be possible (or even wanted!) to always activate in 7/4 time.

I believe that all of this makes optimization a chore and I also believe that figuring all of this out takes an exceptional amount of time. You can do it by hand, but even then you use heuristics.

Maybe I'm making an NP out of a P, though...