# 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 < 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?
• At a first glance, smoothed analysis seems relevant. – Discrete lizard Jun 29 '19 at 19:33
• In the other direction, there are so-called stable instances. – Yuval Filmus Jun 29 '19 at 19:42

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.