A problem X is NP-hard if every problem in NP can be reduced to X. But every problem in NP has a polynomial time verification algorithm, so then does that not mean that I can also verify X in polynomial time because every NP problem is reducible to X? Can someone please explain or give an example.
$\begingroup$
$\endgroup$
0
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
0
Here is an abstract definition of the concepts NP-hard and NP-complete. If $A,B$ are two decision problems, say that $A \leq B$ if there is a polytime reduction from $A$ to $B$, that is, if there exists a polytime function $f$ such that $x \in A$ iff $f(x) \in B$. Then: $$ \begin{align*} &\mathsf{NP\text{-}hard} = \{ B : A \leq B \text{ for all } A \in \mathsf{NP} \}, \\ &\mathsf{NP\text{-}complete} = \mathsf{NP\text{-}hard} \cap \mathsf{NP}. \end{align*} $$
Here is a different example. Consider the universe of all subsets of $\mathbb{N}$, ordered under $A \leq B$ if $A \subseteq B$. Let $\mathsf{X}$ consist of all subsets of some fixed set $X$. Define $\mathsf{X\text{-}hard}$ and $\mathsf{X\text{-}complete}$ just as above. You can check that $$ \begin{align*} &\mathsf{X\text{-}hard} = \{ S : S \supseteq X \}, \\ &\mathsf{X\text{-}complete} = \{ X \}. \end{align*} $$ In a similar way, NP-hardness is a lower bound on the difficulty, whereas NP-completeness is both a lower bound and an upper bound. In contrast to the second example above, there are many NP-complete problems, all of them having the same level of difficulty (two problems $A,B$ have the same level of difficulty if $A \leq B \leq A$).
Finally, here is a concrete problem which is NP-hard but not NP-complete: the halting problem.
The halting problem is NP-hard. Let $A$ be any computable decision problem, say computed by a Turing machine $M$ which always halts. Let $M'$ be the Turing machine which simulates $M$, halts if $M$ accepts, and runs into an infinite loop if $M$ rejects. Define a polytime function $f$ by $f(x) = (\langle M' \rangle,x)$. Then $x \in A$ iff $M$ accepts $x$ iff $M'$ halts on $x$ iff $f(x) \in \mathsf{HALT}$.
The halting problem is not in NP. The halting problem is not computable, and in particular not in NP.
answered May 23, 2017 at 12:03
$\begingroup$
$\endgroup$
1
But every problem in NP has a polynomial time verification algorithm, so then does that not mean that I can also verify X in polynomial time because every NP problem is reducible to X?
No. If a problem $P$ is polynomial-time reducible to $X$, it means that a solution for $X$ can be used to solve problem $P$ (in no more time that is required to find the solution for $X$), and not necessarily that a solution for $P$ may be used to solve problem $X$ (unless $X$ is also polynomial-time reducible to $P$). Provided, clearly, that those problems require at least a polynomial-time algorithm to find their solution. In other words, $X$ is at least as hard as $P$, that is we have an upper bound of the hardness of $P$.
You need to think about the reduction as a mapping: whenever you have a solution for $X$, you also have a solution for $P$. A more accurate definition of what a reduction is can be found here.
-
$\begingroup$ It's a bit misleading when you say that a solution for X can be used to solve problem P without further time, since (1) the reduction takes time, and (2) the reduction could blow up the instance (by a polynomial amount). $\endgroup$ May 23, 2017 at 18:25
$\begingroup$
$\endgroup$
An NP-hard problem can be beyond NP. The polynomial-time reduction from your X to any problem in NP does not necessarily have a polynomial-time inverse. If the inverse is harder, then the verification is harder.
An NP-complete problem, on the other hand, is one that is NP-hard and itself in NP. For these, of course, there exist polynomial time verifications.
$\begingroup$
$\endgroup$
Can someone please explain or give an example?
I'll give an example.
A clique in an undirected graph $G=(V,E)$ is a subset $V' \subseteq V$ of vertices, each pair of which is connected by an edge in $E$. In other words, a clique is a complete subgraph of $G$. The size of a clique is the number of vertices it contains.
The clique optimization problem is the problem of finding a clique of maximum size in a graph.
The clique decision problem is simply whether or not a clique of size $k$ (given input) exists in the graph.
The clique decision problem is in NP-complete, although the clique optimization problem is in NP-hard.
We can reduce from the clique decision problem to the clique optimization problem in polynomial time. This is easier, we simply solve the optimization problem, then check that the size of the maximum clique is greater than or equal to $k$. This is because of a simple relation: any clique of size $n$ contains a clique of size $n-1$.
We cannot verify the clique optimization problem in polynomial time. If the optimization problem is given a certificate, we can verify that the certificate is a clique in polynomial time (similar to the decision problem), but we cannot verify that the certificate is a maximum clique in polynomial time. Thus it is only in NP-hard, not in NP.
Generally speaking, a lot of problems in NP-hard are optimization problems because it is difficult to verify that a certificate for the problem is in fact optimal.
$\begingroup$
$\endgroup$
It is actually enough if one NP complete problem X can be reduced in polynomial time to a problem Y to make Y NP-hard. (Because every problem in NP can be reduced to any NP complete problem).
Most problems can be viewed as special cases of a harder problem. If problem A is a special case of a harder problem B, then there is a reduction from problem A to problem B that isn't just polynomial time, but zero time.
Think about the consequence of what you are saying: If Y had to be in NP, then it would be impossible to have an NP-complete problem that is a special case of a more general problem that is not in NP.
