NP-completeness

There’s no easy way to tell if a problem is NP-complete. Here are some giveaways:

• Your algorithm runs quickly with a handful of items but really slows down with more items.
• “All combinations of X” usually point to an NP-complete problem.
• Do you have to calculate “every possible version” of X because you can’t break it down into smaller sub-problems? Might be NP-complete.
• Can you restate your problem as the set-covering problem or the traveling-salesperson problem? Then your problem is definitely NP-complete.