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

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}$$.

• Please don't delete your question after receiving an answer. Part of our mission is to build up an archive of high-quality questions and answers that will be useful to others in the future, and answerers may be answering on that basis, so deleting the question after receiving an answer might be considered impolite to answerers.
– D.W.
Feb 2 at 18:41

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}$$.