Consider a job schedule decision problem with only one machine takes input $\{(r_1,p_1,d_1),(r_2,p_2,d_2),...,(r_n,p_n,d_n),K\}$; where $r_i$ is the start time for the ith triple, and $p_i$ is the process time of the triple; and $d_i$ is the deadline.Require for each $i$, schedule a job at time $t_i$ such that $r_i≤t_i≤d_i−p_i$. Goals to decide whether we can schedule $K$ number of compatible jobs.
I try to show that this problem is at least as hard as SubsetSum problem.
Consider a instance of input to SubsetSum. $\{a_1,a_2,..a_n;T\}$
Assume that $∃ I⊆\{1,2,..n\}$ such that $∑_{i∈I}a_i=T$; then we can design a transformation such that assigns a subset $\{r_i,p_i,d_i\}$ some value, and show that taking this set as input to schedule problem will also return True. For example, assign start value to each of job to be 0, process time for each job to be $a_i$, deadline for each job to be $\sum_{i\in I} a_i$. I have prove the $\implies$ direction
However, my problem here is about doing converse proof. We have to show that schedule decision problem taking an instance return true implies that SubsetSum taking kind of "inverse transformation" of that instance also returns true.
My understanding of prove converse direction is that we need some sort of inverse transformation. For example, given any arbitrary set of triple $\{(r_i,p_i,d_i)\}$, if this set accepted by schedule problem, then we need to find some "inverse transformation" transform the triples into some array, and a target value that can be accepted by SubsetSum. And this "inverse transformation" compose with our original transformation (designed for ($\implies$) direction proof) should be some identify transformation.
OR
Can we only give the input that has start value to each of job is 0, process time for each job is $p_i$, deadline for each job to be $\sum_{i\in I} p_i$. Basically, use the transformed input from the direction of ($\implies$)
And assume that this set of input accepted by schedule decision problem, we want to show that using the sum over process time and the deadline time as input to SubsetSum can also return true.
I don't which approach is correct here