-2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ We also have a very well-regarded reference question on these terms. $\endgroup$
    – Kyle Jones
    Mar 26 at 16:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Mar 26 at 19:52
  • $\begingroup$ Does this answer your question? What is the definition of P, NP, NP-complete and NP-hard? $\endgroup$
    – Evil
    Mar 28 at 0:10
  • $\begingroup$ @Evil I am aware of that link but i cant find any answer from that link. $\endgroup$
    – user
    Mar 29 at 6:53
3
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – user
    Mar 29 at 6:50
  • $\begingroup$ The first one isn’t really a definition. What does it mean to be more difficult than any problem in NP? $\endgroup$ Mar 29 at 7:07
  • $\begingroup$ Could you please give any reference? $\endgroup$
    – user
    Mar 29 at 7:11
  • $\begingroup$ You’ll have to trust me. $\endgroup$ Mar 29 at 7:11
  • $\begingroup$ 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 $\endgroup$
    – user
    Mar 29 at 7:16
1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Then, what the wiki page mean here: "Lattice problems are an example of NP-hard problems $\endgroup$
    – user
    Mar 26 at 21:53
  • $\begingroup$ It roughly means "more difficult than any problem in $NP$". $\endgroup$
    – Nathaniel
    Mar 26 at 21:56
  • $\begingroup$ Thanks. You really answered my question. Then the all definitions starting "the decision problem is NP-hard if ..." are wrong. $\endgroup$
    – user
    Mar 26 at 22:45
  • $\begingroup$ Another question: Can you verify your answer by references. Is there a standart reference for this topic. $\endgroup$
    – user
    Mar 26 at 22:47
  • $\begingroup$ 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…" $\endgroup$
    – Nathaniel
    Mar 26 at 22:48

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.