Three of your friends work for a large computer-game company, and they ve been working har...

Three of your friends work for a large computer-game company, and they ve been working hard for several months now to get their proposal for a new game, Droid Trader! , approved by higher management. In the process, they've had to endure all sorts of discouraging comments, ranging from "You're really going to have to work with Marketing on the name" to "Why don t you emphasize the parts where people get to kick each other in the head?"

At this point, though, it s all but certain that the game is really heading into production, and your friends come to you with one final issue that s been worrying them: What if the overall premise of the game is too simple, so that players get really good at it and become bored too quickly?

It takes you a while, listening to their detailed description of the game, to figure out what s going on; but once you strip away the space battles, kick-boxing interludes, and Stars-Wars-inspired pseudo-mysticism, the basic idea is as follows. A player in the game controls a spaceship and is trying to make money buying and selling droids on different planets. There are n different types of droids and k different planets. Each planetp has the following properties: there are s(j, p) > 0 droids of type j available for sale, at a fixed price of x(j, p) > 0 each, for j = 1,2,n; and there is a demand for d(j, p) > 0 droids of type j, at a fixed price of y(j, p) > 0 each. (We will assume that a planet does not simultaneously have both a positive supply and a positive demand for a single type of droid; so for each j, at least one of s(j, p) or d(j, p) is equal to 0.)

The player begins on planet s with z units of money and must end at planet t; there is a directed acyclic graph G on the set of planets, such that s-t paths in G correspond to valid routes by the player. (G is chosen to be acyclic to prevent arbitrarily long games.) For a given s-t path P in G, the player can engage in transactions as follows. Whenever the player arrives at a planet p on the path P, she can buy up to s(j, p) droids of type j for x(j, p) units of money each (provided she has sufficient money on hand) and/or sell up to d(j, p) droids of type j for y(j, p) units of money each (for j= 1,2,...,n). The player s final score is the total amount of money she has on hand when she arrives at planet t. (There are also bonus points based on space battles and kick-boxing, which we ll ignore for the purposes of formulating this question.)

So basically, the underlying problem is to achieve a high score. In other words, given an instance of this game, with a directed acyclic graph G on a set of planets, all the other parameters described above, and also a target bound B, is there a path P in G and a sequence of transactions on P so that the player ends with a final score that is at least B? We'll call this an instance of the High-Score-on-Droid-Trader! Problem, or HSoDT! for short.

Prove that HSoDT! is NP-complete, thereby guaranteeing (assuming P ≠ NP) that there isn't a simple strategy for racking up high scores on your friends game.