Consider the following problem, which can be called "2-SET-PARTITION":
Given two sets of positive numbers, $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$, where $\sum_{i\in[n]}a_i = \sum_{i\in[n]}b_i = 2 S$, decide whether there exists a subset of indices $I\subseteq [n]$ such that: $\sum_{i\in I} b_i \geq S \geq \sum_{i\in I} a_i$.
It is easy to prove that this problem is NP-hard by reduction from PARTITION:
Given an instance $p_1,\ldots,p_n$ of PARTITION, create an instance of 2-SET-PARTITION with: $\forall i\in[n]: a_i = b_i = p_i$. Obviously the answer to the first problem is "yes" if and only if the answer to the second problem is "yes".
But, this proof considers only a small subset of the 2-SET-PARTITION --- the subset in which the two sets of integers are equal. Theoretically, it could be that a "typical" instance of the problem is easy: it could be that there is a subset of instances, which includes all instances except a subset of measure zero, in which 2-SET-PARTITION can be decided in polynomial time. There are similar problems in which this is the case.
To prove that this is not the case with 2-SET-PARTITION, one can use the following reduction:
Fix some vector of perturbations, $e_1,\ldots,e_n$, such that $\sum_{i\in [n]} e_i < 1/2$. Given an instance $p_1,\ldots,p_n$ of PARTITION, create an instance of 2-SET-PARTITION with: $\forall i\in[n]: a_i = p_i, b_i = p_i + e_i$. Here, too, it is possible to show that the answer to the first problem is "yes" if and only if the answer to the second problem is "yes".
Intuitively, the second proof is much stronger than the first, because it shows that even arbitrary perturbations cannot make the problem easy.
MY QUESTIONS:
- What is a term for this stronger NP-hardness concept, that is robust to perturbations?
- What are some references showing proof techniques for this hardness concept?
