Hello,
As I am doing my graduate project and I choose to do the clique problem, I have a few questions about NP-hardness. I have read this post, but I didn't find answers on my questions.
First question: Suppose we can find a problem X that hasn't a polynomial solution and which is not a decision problem. We have to put this problem to the NP-hard set. But if we also cannot find any NP-complete problem Y, such that Y is reducible to our problem X in polynomial time, then X shouldn't belong to NP-hard set. Where shall we put this problem X? Or such a problem cannot be found?
Second question: It's known that problems like the longest path and maximum clique in a graph are NP-hard and they do not have verifier in polynomial complexity. Their decision problems are NP-complete (path of length k, or clique of length k). But, we can easily transform one to another — for example, find maximum clique with checking values for k = 1 up to n and take maximum with the existing clique. So why those problems are not np-complete too? Is the only reason because they are not decision problems? Also why we need a polynomial verifier for maximum clique problem, as we can solve it with calling clique of length k, n times and we can verify that problem in polynomial time? So we know that answer is correct, otherwise, our polynomial verifier for a clique of length k is not correct.
Thanks in advance! :)
NP-hard is about decision problems only. No "buts".
When people say something like "knapsack is NP-hard" what they really mean is "some small variation to knapsack which makes it a decision problem is NP-hard".
Hi, thank you for answering.
I am a little bit confused now, as the most upvoted comment in the post state that NP-hard doesn't have to be a decision problem.
But still, if we cannot reduce our NP problem X, and cannot find any NP-complete problem which is reducible to X, where we need to put problem X?
Also, if the decision is not the reason for putting in the NP-hard, why are the maximum clique or longest path NP-hard?
The decision problem of clique is, given a graph G and integer k, does there exist a clique of size k.
The decision problem of longest path is, given a graph G and integer k, does there exist a simple path of length k.
It is easy to solve the maximum clique or longest path, using the above decision problems, some polynomial amount of times, so you can think of these as the same problem. Still, by definition, we only talk here about decision problems.
Edit: as for your second question; perhaps we can formulate the maximum clique problem you describe, as given a graph and a clique, is this clique maximum (note that this is a decision problem now). I don't know if we already know about a polynomial verifier for this, but I feel like it would imply P = NP.
Edit2: actually, the above mentioned decision problem has a polynomial nondeterministic solver that just tries all subsets... so it's NP. What is the definition of maximum clique you have in mind?
I have a small doubt.
What I understood from the article is, if we manage to find a "deterministic polynomial time solution" to any one NP-Hard problem, then that means we found the solution to every NP problem but not for every NP-Hard problem? Is it correct?
Solving one NP-Hard problem is independent of solving other NP-Hard problems?
It is generally true, not all NP-Hard problems are solvable at all. For example, Halting problem is NP-Hard.
Thanks for the reply!
Btw, how do I know if a problem is NP-Hard? Is there any general characteristic or we have to prove it differently for each problem?
If you can reduce any other NP-Hard problem to it then it's also NP-Hard. Don't know any better way.
Thanks for clearing my doubts. :)
If you can reduce any other NP-Hard problem to it
Nope. This is not complete. The reduction must be able to be done in Polynomial time. Otherwise, your reduction is kind of pointless.
Surely by reduce I meant Karp reduction, it's the default one when we talk about NP-Hard class.
If you can reduce any problem from NP, not every NP-Hard problem. (You don’t want halting problem be reducible to TSP.)
I didn't say every NP-Hard problem, I said "any other" NP-Hard problem... It means that reducing one (arbitrary) problem which is known to be NP-Hard is enough.
Understood. Hopefully, I’m not the only one who sees implied universal quantification there.
There are easy problems that you can turn into NP-complete ones via “small variation”, so no, that’s not what those people really mean.
Informal “knapsack is NP-hard” is a shorthand for “solving knapsack is as hard as solving arbitrary problems from NP”, which is formalized as “any solver for knapsack can be turned into a solver of any NP problem with only polynomial overhead”.