The last paragraph of Section 17.2.3 discusses a strategy for developing a solution to a new problem by alternating between finding a polynomial time solution and proving the problem \(\mathcal{N P}\)-complete. Refine the "algorithm for designing algorithms" from Section 15.1 to incorporate identifying and dealing with \(\mathcal{N} \mathcal{P}\)-complete problems.

Transcribed Image Text:

17.2.3 Coping with NP-Complete 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? 21 X2 C 12 13 18 23 C C3