How to prove that this problem is NP-complete (or NP-Hard)

Question

I have the following data:

• A set $V$ of tasks, the starting time $s_j$ of each task and the duration $p_j$ of each task.

• A set $K$ of resource, each resource has an availability function $R_{k}$ that is piecewise constant.That is, for each $t = 0, .., T-1$, we precise $R_{k}(t)$ the number of units available at $t$. $R_k$ is an array of length $T$.

• Each task $j$ needs $r_{j,k}$ resources to be processed (it could be zero). This quantity needs to be available during all the processing time starting from $s_j$.

For example consider :

• Task$A$ has processing time $3$ and starts at time period $t=2$ and needs 2 units of some resource $k$
• Task $B$ has processing time $4$ starts at time $t=3$ and needs 3 units of the same resource $k$.

Then if $R_{k}(t) = [*,*,2,6,6,3,*,*]$ then we are ok since at time $t=2$ only task $A$ is active and it requires $2$ units, at time $t=3$, both tasks are active and the sum of their utilization is $2+3 = 5 \leq 6$; same at time $t=4$. At time $t=4$, only task $B$ is active and it requires $3$ units.

However, if $R_{k}(t) = [*,*,2,4,6,3,*,*]$, is not ok since at time $t=3$, both tasks $A$ and $B$ are active and their total use is equal to $5$ wheras only $4$ units are available.

Here is my attempt to verify that the resource utilization at each $t$ is no larger than the availability function. So the answer is yes or no (we can say that this is a decision problem).

For each time t in [0,T-1]
  For each resource k in K 
    total_use = 0, active_set = A
    for each task j in V
      if s_j<=t and s_j+p_j > t and r_{j,k}>0 \\if the task is active at time t and it requires positive amount of resource k in order to be processed)
        total_use += r_{j,k}
        active_set := active_set U {j} 
      if total_use > R_{k}(t)
        print(at time t the usage of resource k exceeds its capacity, active_set)
        return False
return True

The algorithm here is pseud-polynomial. Unfortunately, I need to find a polynomial one in order to say that the problem is in $\mathcal{NP}$.

Answer 1

You may think that your algo is pseudo-polynomial because the outer loop repeats $T$ times and the possible size of $T$ grows exponentially with a bit string describing $T$. But notice that $R_k(t)$ is given for $t\in[0,T-1]$ (in your input) meaning that your input grows $\Omega(kT+|V|)$ and the runtime of the algo is $O(Tk|V|)$ (disregarding log factors from the set operations etc.). Hence, the runtime grows polynomial with respect to the input size.

As a result your decision problem lies in $\mathcal{P}$.