I am reading some papers in machine learning and at the very beginning (introduction) you will see statements of theorems that says, for example:

Theorem 1.1. For any constant ϵ > 0, it is NP-hard to find a halfspace that correctly labels (1/2 + ϵ)-fraction of given examples over {0, 1} n even when there exists a monomial that agrees with a (1 − ϵ)-fraction of the examples. https://people.eecs.berkeley.edu/~prasad/Files/mono.pdf

At this point, the definition of NP-hard is not even defined. I have seen many examples like this, which makes me wonder

"Do all these thousands of authors have the same definition of NP-hard/complexity notions"?

"These contexts seem so different from the usual contexts where NP-hardness come up such as graph coloring or traveling salesman problem, how can I be sure that these notions of complexity/NP hardness are equivalent?"

Can someone point out a good reference for studying complexity theory in a machine learning/operation research/optimization context? Many thanks!

  • $\begingroup$ Why would they not be equivalent? $\mathsf{NP}$-hardness is a very well known concept in theoretical CS and I'd say almost all CS students will encounter one of the usual ways to define it at some point. The last sentence of the abstract says that their result is derived by reducing the problem at hand to some (presumably $\mathsf{NP}$-complete) problem, which is exactly how pretty much every $\mathsf{NP}$-hardness proof I know of works. $\endgroup$ Oct 7, 2020 at 4:02
  • 1
    $\begingroup$ Please ask only one question per post. If you have multiple questions, you can post them separately. Book recommendations are usually not suitable here. I suggest doing more research before asking; NP-hardness is a standard topic that you should be able to find a lot about, and doing a little research should quickly identify several excellent books on complexity theory. It might help to show what you've come up with so far and why you've rejected it. See cs.stackexchange.com/help/how-to-ask. $\endgroup$
    – D.W.
    Oct 7, 2020 at 6:13

1 Answer 1


In modern papers, and unless stated otherwise, NP-hardness is one of the following:

  • A decision problem is NP-hard if it is NP-hard with respect to many-one reductions.
  • An optimization problem is NP-hard if its decision version is NP-hard.

Sometimes, more informal notions are used. The most common one is probably hardness of approximation. When a theorem states that maximization problem X is NP-hard to approximate within a factor of $\alpha < 1$, it usually means that there is a many-one reduction from SAT (or some other NP-complete problem) an instance of X and a parameter $k$ such that

  • If the original SAT instance is satisfiable, then the value of the X-instance is at least $k$.
  • If the original SAT instance is unsatisfiable, then the value of the X-instance is at most $\alpha k$.

However, to be sure, you need to look at the exact statement being proved.

Your case is similar. The complete version of your paper proves the main theorem in Section 5. Theorem 5.2 on page 21 states exactly what holds in the Yes case and what holds in the No case (Theorem 5.1 shows that it is NP-hard to distinguish the two cases). You should be able to relate this to the informal statement appearing in Theorem 1.1.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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