What does "NP-hard to distinguish ... between ... and ..." mean?

Question

I am reading paper Hardness Results for Weaver’s Discrepancy Problem. In the abstract, the paper reads

it is NP-hard to distinguish such a list of vectors for which there is a signed sum that equals the zero matrix from those in which every signed sum has operator norm at least $\kappa \sqrt{\alpha}$, for some absolute constant $\kappa >0 $.

How to define 'to distinguish A from B'? What kind of the problem that does that belongs to? I searched that in Google, but I did't find definitions like that. Problems like decision problems or optimization problems have precise definitions and can be stated in the mathematical language. But what is 'to distinguish sth. from sth.'?

Answer 1

This is a promise problem.

In this case, we promise that either every sum has operator norm at least $\kappa\sqrt\alpha$, or there will be a sum of $0$. (That is, the input is restricted to be chosen from the set of lists of vectors that satisfy this either-or condition.) We do not require the algorithm to do anything in particular if the input does not satisfy this condition.

Aside from restricting the input, the promise problem works as an ordinary decision problem. (We can phrase the decision problem in multiple ways, but one way is "is there a signed sum of the input equal to $0$?")

We consider promise problems for a variety of reasons, such as:

• Sometimes, the promise is a natural subclass of inputs. (E.g. searching for shortest paths in directed graphs without negative cycles.)
• Sometimes, in complexity theory, even the promise problem is hard, which sheds light on why the decision problem is hard.
• Sometimes, we want to explore the boundary of what kind of promise will make the problem easy.

Answer 2

"Distinguish from" is like a search problem, but allows for non-constructive answers for whether the search would be successful.

In other words, "find a signed sum over the outer products of these vectors that is equal to 0" is a search or combinatorial or integer optimization problem, which may have no solution.

"Distinguish from" allows for algorithms that determine if a solution exists without actually finding one.

A very different example might be "distinguish those Mersenne numbers that can be factored from those that can't". The Lucas-Lehmer test will tell you when you have a Mersenne prime, but actually factoring is much harder.