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.

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

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