5
$\begingroup$

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.