There are several ways that a problem could be considered hard. For example, we might have trouble understanding the definition of the problem itself. At the beginning of a large data collection and analysis project, developers and their clients might have only a hazy notion of what their goals actually are, and need to work that out over time.

Recall that a problem is said to be NP-hard if any problem in NP can be reduced to it in polyonomial time.

It might seem impossible that any problem could actually be NP-hard, let alone provably so. But in fact there are hundreds of such problems, including TRAVELING SALESMAN. Another such problem is called K-CLIQUE.

Recall that to prove a problem NP-complete, we must prove that it is in NP, and that it is NP-hard. To prove that it is in NP, we usually provide a NP algorithm. This is typically easy: Check in polynomial time that a guessed answer is correct. To prove that the problem is NP-hard, our normal process is to find some known NP-hard problem and reduce it to our problem.

Thus, to start the process of being able to prove problems are NP-complete, we need to know that some problem H is NP-complete. After that, every problem proven NP-complete gives us another problem available to use in future proofs of other problems.

Finding that your problem is NP-complete might not mean that you can just forget about it. Traveling salesmen need to find reasonable sales routes regardless of the complexity of the problem.

What do you do when faced with an NP-complete problem that you must solve?