NP-hardness even with perturbations 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 &lt; 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?
If you allow arbitrary $e_i$, you are in muddy ground. Are your numbers real? No way to express them finitely, NP-whatever right out the window. Rational? The input size can blow up almost arbitrarily, again nothing relevant to prove.

Note that (for very good reasons) NP-hard and its ilk talk about the worst case complexity of the problem (that is well-defined, opposed to say avergage complexity; best-case essentially tells nothing in most interesting cases). That some proof gives just one particular hard case for particular sizes, while another gives a bevy of them, is irrelevant.