NP-Complete refers to the hardest known problems within the complexity class NP. The "Traveling salesman problem" is one of the most widely known NP-Complete problems.
The classic method of attacking NP-complete problems is to try and prove that P = NP. Once a PTIME solution has been proven to exist for at least one NP-complete problem, that could be used to solve all of the others via reduction.
This is an active area of research. Communications of the ACM Volume 52, Number 9 (2009), Pages 78-86: The Status of the P vs NP Problem gives a good overview of the problem and current approaches to resolving it. (The article is freely available here.)
Apart from that, there are some approaches that can be used to get useful—although not optimal—solutions to NP-complete problems in practice:
- Brute force
- Heuristics that produce "reasonably good" results most of the time
- Arbitrary approximation algorithms that can produce increasingly better solutions the longer they are allowed to run
- Genetic algorithms, which try to find multiple "reasonably good" solutions and then "mutate" these solutions to get even better solutions.
