Confused about NP-Complete Proof Using Reduction

Question

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

Answer 1

Your solution is a far way off from being correct. It seems that you are trying to use different transformations for both directions of the proof, while you should actually be using a single transformation from subset sum to the scheduling problem.

I try to show that this problem [scheduling] is at least as hard as SubsetSum problem.

Subset Sum is a hard problem; we don't think it's likely that it can be solved in polynomial time. If you want to show that scheduling is hard, then you need to show that if we could solve scheduling in polynomial time, then we can also solve subset sum in polynomial time.

What you are given is an instance of subset sum $\{a_1,a_2,\ldots, a_n; T\}$ and a magic machine that somehow solves the scheduling problem in polynomial time. We want to show that it is unlikely that this magic machine could exist, therefore we will show that using this magic machine we can solve subset sum in polynomial time (which we think is probably not possible).

For this, you need a transformation that takes an instance $A$ of subset sum as input, and gives as output an instance $B$ of the scheduling problem, such that $A$ has a feasible solution if and only if $B$ does. That is, being able to find a solution for $B$ (in polynomial time) will also let you find one for $A$ (in polynomial time).

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

You can't do this. You can't base the transformation on the assumption that the subset sum instance is solvable. You don't know $I$ (because this is the hard-to-compute thing you're trying to compute), so you can't use it to construct the transformation. You can only use $I$ to show that, the transformed instance - which you constructed without knowledge of $I$ - has a solution.

Hint: you need to design an instance of the scheduling problem that is forced to split the jobs into two groups (one summing up to $T$, one to $\Sigma a_i - T$). For this, it might be useful to have one or two additional jobs that must be scheduled at a fixed point in time (by setting $r_i+p_i=d_i$).

To summarize: a correct NP-hardness proof consists of the following steps:

1. Take an NP-hard problem (e.g., subset sum) and design a transformation $f$ that maps an instance $A$ of this problem to an instance $B=f(A)$ of the problem you want to show NP-hard (e.g., scheduling).

2. Show that, if $A$ has a solution (is a yes-instance), then $B$ is a yes-instance

3. Show that, if $B$ is a yes-instance, then $A$ is a yes-instance (or show the converse: if $A$ is a no-instance (has no solution) then $B$ is a no-instance as well.