balsa_knez's blog

NP vs NP-complete vs NP-hard
By balsa_knez, history, 4 years ago, In English

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! :)

  • Vote: I like it
  • +50
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

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".

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +15 Vote: I do not like it

      It is generally true, not all NP-Hard problems are solvable at all. For example, Halting problem is NP-Hard.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          If you can reduce any other NP-Hard problem to it then it's also NP-Hard. Don't know any better way.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks for clearing my doubts. :)

            → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              Surely by reduce I meant Karp reduction, it's the default one when we talk about NP-Hard class.

              → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            If you can reduce any problem from NP, not every NP-Hard problem. (You don’t want halting problem be reducible to TSP.)

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Understood. Hopefully, I’m not the only one who sees implied universal quantification there.

                → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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".

    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”.

    → Reply