<p>Suppose that there was a polynomial time algorithm $A$ for your promise problem, say with time complexity bounded by $const*|U|^a*m^b$.</p>

<p>Take an arbitrary instance of SET-PACKING (the original variant, not the priomise variant) and run algorithm $A$ on it for $2*const*|U|^a*m^b$ steps.
If $A$ does not terminate within this time bound, the answer must be NO.
If $A$ does terminate, verify whether the output produced by $A$ indeed is a feasible solution.</p>

<p>This would allow you to solve the original SET-PACKING problem in polynomial time.</p>

CC BY-SA 3.0
2015-01-12T19:56:05.300Z
I'd say something like this - if the algorithm throws an exception or does not accept instances for which SET-PACKING is no: it's able to distinguish between yes and no instances of SET-PACKING. If it accepts either yes or no instances of SET-PACKING, and just returns meaningful input on yes instances, then it is able to decide SET-PACKING (here the fact that SET-PACKING is in NP is important, since it allows us to verify output feasibility in poly-time).
Spark
CC BY-SA 3.0
2015-01-12T19:41:56.053Z
2015-01-12T19:41:56.053Z
Gamow
<p>An instance of the SET-PACKING problem is given by a list of sets $\mathcal{S} = \{S_1,\dots,S_m\} \subseteq 2^U$. It is a ``yes'' instance iff there exists some subset $\mathcal S'$ of $\mathcal S$ of size $\ge k$ such that for every $S,T \in \mathcal S'$, $S\cap T = \emptyset$. </p>

<p>Now, I propose the "promise variant" of this problem: I am telling you that your instance is a yes instance; that is, there exists some $\mathcal T'\subseteq \mathcal S$ such that all elements of $\mathcal T'$ are disjoint and it is of size $\ge k$. Can you find some $\mathcal S'$ that is of size $\ge k$ with all disjoint elements?</p>

<p>This seems to be an obviously NP-hard problem, but one needs to be slightly careful in the proof: intuitively, simply taking an instance of SET-PACKING and appending k arbitrary disjoint sets will work (informally, if finding them is in P, then SET-PACKING is also in P).</p>

<p>This relates to a similar question that appeared in cs.stackexchange. I am aware that promise variants of NP hard problems are generally hard (that is, given an NP hard problem X, define promise-X to be the problem X when a yes instance is guaranteed).</p>

<cc.complexity-theory><reference-request>
Promise Variant of Set-Packing
Spark
# Promise Variant of Set-Packing

(Asked by: username_0 on 2015-01-12)

An instance of the SET-PACKING problem is given by a list of sets $\mathcal{S} = \{S\_1,\dots,S\_m\} \subseteq 2^U$. It is a ``yes'' instance iff there exists some subset $\mathcal S'$ of $\mathcal S$ of size $\ge k$ such that for every $S,T \in \mathcal S'$, $S\cap T = \emptyset$.

Now, I propose the "promise variant" of this problem: I am telling you that your instance is a yes instance; that is, there exists some $\mathcal T'\subseteq \mathcal S$ such that all elements of $\mathcal T'$ are disjoint and it is of size $\ge k$. Can you find some $\mathcal S'$ that is of size $\ge k$ with all disjoint elements?

This seems to be an obviously NP-hard problem, but one needs to be slightly careful in the proof: intuitively, simply taking an instance of SET-PACKING and appending k arbitrary disjoint sets will work (informally, if finding them is in P, then SET-PACKING is also in P).

This relates to a similar question that appeared in cs.stackexchange. I am aware that promise variants of NP hard problems are generally hard (that is, given an NP hard problem X, define promise-X to be the problem X when a yes instance is guaranteed).

**Tags:** cc.complexity-theory, reference-request

---

## 1 answers

### Answer by username_1 on 2015-01-12. Score: 1 | Accepted answer

Suppose that there was a polynomial time algorithm $A$ for your promise problem, say with time complexity bounded by $const\*|U|^a\*m^b$.

Take an arbitrary instance of SET-PACKING (the original variant, not the priomise variant) and run algorithm $A$ on it for $2\*const\*|U|^a\*m^b$ steps.
If $A$ does not terminate within this time bound, the answer must be NO.
If $A$ does terminate, verify whether the output produced by $A$ indeed is a feasible solution.

This would allow you to solve the original SET-PACKING problem in polynomial time.

> **Comments:**
> **username_0**: I'd say something like this - if the algorithm throws an exception or does not accept instances for which SET-PACKING is no: it's able to distinguish between yes and no instances of SET-PACKING. If it accepts either yes or no instances of SET-PACKING, and just returns meaningful input on yes instances, then it is able to decide SET-PACKING (here the fact that SET-PACKING is in NP is important, since it allows us to verify output feasibility in poly-time).  

---

