As I understand, to show that a certain problem P is NP-hard we can reduce a known NP-hard problem, Q, to problem in P in polynomial time. To show that the problem P is NP-hard in strong sense, we can reduce a know NP-hard problem Q to problem P in pseudo polynomial time. Is it possible to show that a certain problem P is NP-hard by reducing two known NP-hard problems Q and Q' to a problem in P?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ You seem to be simultaneously using "P" to stand for some arbitrary problem and for the class of problems that can be solved deterministically in polynomial time. Please rewrite your question to make it clear which is which. $\endgroup$– David RicherbyCommented Oct 4, 2014 at 22:08
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
If you can reduce one NP-hard problem to a problem $L$, then $L$ is NP-hard. If you can reduce a second NP-hard problem to $L$, then so what? You already know that $L$ is NP-hard. How could reducing more problems to $L$ make $L$ easier (e.g., not NP-hard)?
It's like saying, "If I have one million dollars, I'm rich. If I have two million dollars, am I still rich?"
answered Oct 4, 2014 at 22:11
-
$\begingroup$ I took a different interpretation of the question. Let's say we could not independently reduce $Q$ to $L$ and we also could not reduce $Q'$ to $L$ (or rather, we don't know these reductions). Although, through some combination of $Q$ and $Q'$ that reduces to $L$. I would assume in this scenario you might need to prove that the combination itself is in NP-hard first, to conclude that $L$ is also in NP-hard. $\endgroup$– ryanCommented May 9, 2017 at 19:47
-
$\begingroup$ @ryan Feel free to post an answer along those lines. But if the asker intended something along those lines, they sure didn't express it clearly! I don't see anything in the question pointing to that interpretation. $\endgroup$ Commented May 10, 2017 at 10:14
$\begingroup$
$\endgroup$
1
A few definitions: a pseudo-polynomial problem is a problem which is polynomial on some parameter but that parameter itself makes the problem NP-complete. For example, unary subset sum is polynomial but the problem size is exponential.
If a problem that is NP-hard can be reduced to a polynomial problem in polynomial time, it would mean that the problem has polynomial complexity P.
To reduce a problem to an NP-hard problem by a polynomial time reduction means that the problem is NP hard.
The Cook-Levin theorem shows that all NP problems can be reduced in polynomial time to a problem in NP-complete.
So there is no guarantee that an NP-hard problem can be reduced to an NP-hard problem, but it may.
-
$\begingroup$ "To reduce a problem to an NP-hard problem by a polynomial time reduction means that the problem is NP hard." This is incorrect. Any problem in NP, including trivial ones such as $\emptyset$ can be reduced to any NP-hard problem. But $\emptyset$ is certainly not NP-hard. $\endgroup$ Commented Dec 16, 2014 at 17:04