Grötschel, Lovász, and Schrijver weigh in on the “Is TSP NP-complete?” debate

It’s just semantics.

In last month there’s been a little debate regarding whether or not the Traveling Salesman Problem (TSP) is NP-complete. Puget argues that it is not, because he’s thinking of the optimization version of TSP. Fortnow clarifies that there is a standard decision problem associated with the TSP that is NP-complete and isn’t bothered with the technicalities. Since this is my blog I’ll also link to my response.

Grötschel, Lovász, and Schrijver are sympathetic to Fortnow’s viewpoint in Geometric Algorithms and Combinatorial Optimization:

Since we do not want to elaborate on the subtle differences between the various problem classes related to the class NP we shall use the following quite customary convention. In addition to all decision problems that are NP-complete, we call every optimization problem NP-complete for which the associated decision problem is NP-complete.

I realize my opinion means nothing compared to that of greats like Fortnow, Grötschel, Lovász, and Schrijver. Still, I sit on the “let’s try to be precise” side of this debate.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s