CODEWITHSUNDEEP
complexity-theory
Chandler Bong
Chandler Bong

Reputation: 461

NP-complete problems

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?

Upvotes: 0

Views: 150

Answers (2)

Nuri Tasdemir
Nuri Tasdemir

Reputation: 9842

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.

Upvotes: 2

MrSmith42
MrSmith42

Reputation: 10151

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.

Upvotes: 0

Related Questions