I have come into NP-complete problems and I can't tell when the problem is NP-complete. Is there a shortcut to know whether a given problem is NP-complete or not so that I don't waste time thinking about a fast algorithm?

CodePudding user response：

The only easy way to show that a problem is NP-Hard is to convert an already known NP-complete problem into this problem in polynomial time. Meaning the conversion should be calculated in polynomial time with respect to the size of the input. In this case, you know that the problem you have is NP-Hard, which means it is at least as hard as NP-Complete but may be more difficult.

At this point, you could stop trying to find a solution for it.

But if you also need to show that it is NP-complete, then you need to show that a solution could be check in polynomial time.

CodePudding user response：

There is no easy way.

If you can transform a known NP-complete problem in an instance of your problem in polynomial time, than you know that your problem is also an NP-complete problem.

If you cannot find such a transformation, you simply don't know if it is NP-complete.