# Does NP-hard problems have to be decision problems? (What the fact please) (contradicting answers)

Let me explain my trouble by another example.

The wiki page says that

Lattice problems are an example of NP-hard problems

However, by clicking NP-hard, i find this definition

A decision problem H is NP-hard when for every problem L in NP, there is a polynomial-time many-one reduction from L to H.

What the fact? Lattice problems are not decision problems.

Edit after two answers: I think the two answers below have contradicting definitions:

1-)An optimization problem is NP-hard if it is as hard as NP-hard decision problems.

2-) An optimization problem is NP-hard if its decision version is NP-hard.

Which one is the real definition.

• We also have a very well-regarded reference question on these terms. – Kyle Jones Mar 26 at 16:47
• Are you aware that is a link to a "pirated" copy of a copyrighted book? Please don't post links to "pirated" content. Instead, cite the book and give a proper reference: title, authors, chapter, section, page number, etc. – D.W. Mar 26 at 19:52
• Does this answer your question? What is the definition of P, NP, NP-complete and NP-hard? – Evil Mar 28 at 0:10
• @Evil I am aware of that link but i cant find any answer from that link. – user Mar 29 at 6:53

## 2 Answers

In complexity theory, we often concentrate on decision problems. "Officially," NP-hardness is a category of decision problems — only a decision problem can be (or not be) NP-hard.

However, it is also common to use NP-hardness when referring to optimization problems. An optimization problem is NP-hard if its decision version is NP-hard.

In more advanced complexity theory, NP-hardness is used in a less precise way. For example, this paper "give[s] a new proof showing that it is NP-hard to color a 3-colorable graph using just four colors". They also prove that it is NP-hard to distinguish graphs of type A from graphs of type B (see their Theorem 3). What they really mean, in the former case, is that for any problem $$L$$ in NP there exists a polynomial time reduction $$f$$, outputting a graph, such that if $$x \in L$$ then $$f(x)$$ is 3-colorable, and if $$x \notin L$$ then $$f(x)$$ is not 4-colorable.

• I think these two definitions contradicts: 1-)An optimization problem is NP-hard if it is more difficult than any problem in NP 2-) An optimization problem is NP-hard if its decision version is NP-hard. Which one is the real definition. – user Mar 29 at 6:50
• The first one isn’t really a definition. What does it mean to be more difficult than any problem in NP? – Yuval Filmus Mar 29 at 7:07
• Could you please give any reference? – user Mar 29 at 7:11
• You’ll have to trust me. – Yuval Filmus Mar 29 at 7:11
• Yes, I trust you but all the people have to trust you. Since people use different definitions, I cant understand what they mean by NP-hard – user Mar 29 at 7:16

Now that you have edited your post, your question is more clear ('cause let's be honest, it was very confusing before the modifications…)

By definition, problems in $$NP$$ are decision problems. However, $$NP$$-hard problems are not necessarily in $$NP$$ and even not necessarily decision problems.

Let's make an example of this. Consider the following decision problem:

Clique – Input: a graph $$G$$ and an integer $$k$$; Question: is there a subgraph of $$G$$ that is a clique of size $$k$$?

It is well known that Clique is a decision problem in $$NP$$ (and even $$NP$$-complete). Consider now the following optimization problem:

max-Clique – Input: a graphe $$G$$; Maximize: the size a subgraph $$H$$ of $$G$$; Conditions: $$H$$ is a clique.

Now we will prove that max-Clique is $$NP$$-hard, despite not being a decision problem. Indeed, if you know how to solve max-Clique, then given a graph $$G$$ and an integer $$k$$, you can solve Clique$$(G, k)$$ by running max-Clique$$(G)$$ and verifying if the result is greater than $$k$$ or not. This is done in an additionnal polynomial time. That proves that Clique $$\leq_m^p$$ max-Clique. Since Clique is $$NP$$-complete, we conclude that max-Clique is $$NP$$-hard.

• Then, what the wiki page mean here: "Lattice problems are an example of NP-hard problems – user Mar 26 at 21:53
• It roughly means "more difficult than any problem in $NP$". – Nathaniel Mar 26 at 21:56
• Thanks. You really answered my question. Then the all definitions starting "the decision problem is NP-hard if ..." are wrong. – user Mar 26 at 22:45
• Another question: Can you verify your answer by references. Is there a standart reference for this topic. – user Mar 26 at 22:47
• Not necessarily: you can chose to talk about $NP$-hardness only for decision problems. What would be wrong would be "we define a $NP$-hard problem as a decision problem verifying…" – Nathaniel Mar 26 at 22:48