NP-Complete Problems: Definition, Classification & Examples

[Avichal]

As far as I understand NP-complete problems are problems that are NP and have some other problem that is reducible to itself. Basically it is a set of problems that are NP-complete and if one is solved all are solved, right?

What is the point of defining such set of problems? Also there might be several such sets of NP-complete problems, right?

Also, I see that there are even more classification of problems like NP-hard, RE complete etc. Again, what's the point?

 

[SteamKing]

The point is figuring out if such problems can be solved in a reasonably finite amount of time by computers.

http://en.wikipedia.org/wiki/NP-complete

For example, can you use a computer to optimize route planning to determine the least distance traveled to service all stops? Are certain cryptographic systems immune from attack?

For example, the Germans thought their military cipher system Enigma was 'unbreakable' during WWII, and thus used it extensively to transmit all sorts of messages from Berlin to front-line units. However, due to a number of factors, this confidence was misplaced, and the Allies were able to decipher some messages quickly enough to be tactically useful against the Germans.

Nowadays, all sorts of personal and commercial information is encrypted to prevent tampering by third parties. If it were shown that these encryption systems were vulnerable to attack, then crimes like fraud and identity theft, and the losses caused by such activity, would increase dramatically.

 

[Avichal]

The point is figuring out if such problems can be solved in a reasonably finite amount of time by computers.

http://en.wikipedia.org/wiki/NP-complete

For example, can you use a computer to optimize route planning to determine the least distance traveled to service all stops? Are certain cryptographic systems immune from attack?

For example, the Germans thought their military cipher system Enigma was 'unbreakable' during WWII, and thus used it extensively to transmit all sorts of messages from Berlin to front-line units. However, due to a number of factors, this confidence was misplaced, and the Allies were able to decipher some messages quickly enough to be tactically useful against the Germans.

Nowadays, all sorts of personal and commercial information is encrypted to prevent tampering by third parties. If it were shown that these encryption systems were vulnerable to attack, then crimes like fraud and identity theft, and the losses caused by such activity, would increase dramatically.

The practical examples helped. All I read about was 3-SAT, vertex cover etc. Now seeing these examples, I see why such classification of problems is done. Thank You!

 

[Avichal]

One more doubt -
Say we have a problem A that is NP. We have another problem B and A can be reduced to B. So we call A and B NP.
And since both are reducible to each other we collectively call them NP-complete problems. Am I right?

Also we have two more problems C and D. C and D are NP and both are reducible to each other but cannot be reduced to A and B. So will they be called NP-complete problems?

 

[Bill Simpson]

Say we have a problem A that is NP. We have another problem B and A can be reduced to B. So we call A and B NP.
And since both are reducible to each other we collectively call them NP-complete problems. Am I right?

Only if you can show that solving A (or B) means you could then solve all the other problems in the NP Complete "club" with only a modest extra amount of work and vice versa, not otherwise.

Showing your new problem is "equivalent" to all (which actually means any) of the long list of existing NP Complete problems is what it takes to be granted membership.

Saying "I have these two wildly hard problems and if you could solve either then you could solve the other, but I have no idea whether either is harder or easier or completely unrelated to the NP Complete membership list" does not grant your problems membership in the NP Complete club.