A good abstraction makes it easier to think clearly about a problem, and/or makes the problem mechanically easier to solve. Does NP-Completeness make problems easier to solve? Consider the following observations made by the authors of Computers and Intractability:
- Within NP-Completeness it is very difficult to distinguish between similar problems, i.e. Two problems with different running times and structure are nearly indistinguishable. The difference between an NP-Complete problems and non-NP-complete problems is difficult to discern.
- Distinguishing types of problems cannot be reliably done using the theory. That is, we must resort to enumerating them in an indexed list, offering different representations of the problem, and waiting for someone who solves problems to update the list.
- The relationship between particular solution and general case becomes blurry and confusing.
The book is a seminal work in NP-Completeness theory. The authors did not seem to think these observations were a problem. I think they are. Consider a classic problem called
The Traveling Salesman: A Salesman must visit each of n cities. The Salesman has a route: he visits each city in turn. If he starts in Baltimore, he will return to Baltimore once he has visited every other city exactly once. He would like to make this route more efficient. Can we help our salesman out? Given a list of cities, the distances between them, and a map of how the cities connect, can we find the shortest route he can take which visits every city once, and leads back to the place he started?
To solve the problem, say I start calculating combinations at random. Consider two possible outcomes:
1) On the first try I have the answer: Each city connects to each other by the two shortest connections; there is no way to have a shorter route, and this route satisfies my other criteria. Answer in hand, I am done.
2) Partway through, I reach a dead-end. He is in Denver, has cities left to visit, but has already visited every city with a direct connection to Denver. Any way he leaves, he will pass through a city for the second time, before reaching a new one. He is trapped.
In the second case, I still don't know if such a tour is possible. Which leads me to the following
According to Computers and Intractability, Yes, it should, and it appears that problems of this kind violate the law of logical complement.
However, the answer is No.
Why? {The answer can be found here}
■Q2: Can the law of logical complement be violated?
The Traveling Salesman: A Salesman must visit each of n cities. The Salesman has a route: he visits each city in turn. If he starts in Baltimore, he will return to Baltimore once he has visited every other city exactly once. He would like to make this route more efficient. Can we help our salesman out? Given a list of cities, the distances between them, and a map of how the cities connect, can we find the shortest route he can take which visits every city once, and leads back to the place he started?
To solve the problem, say I start calculating combinations at random. Consider two possible outcomes:
1) On the first try I have the answer: Each city connects to each other by the two shortest connections; there is no way to have a shorter route, and this route satisfies my other criteria. Answer in hand, I am done.
2) Partway through, I reach a dead-end. He is in Denver, has cities left to visit, but has already visited every city with a direct connection to Denver. Any way he leaves, he will pass through a city for the second time, before reaching a new one. He is trapped.
In the second case, I still don't know if such a tour is possible. Which leads me to the following
TWO QUESTIONS
■Q1: If I have asked my question in such a way that a positive result for a single instance tells me, "yes there is such a solution and this instance is such a solution", shouldn't a negative answer to an instance tell me, "no, there is no such solution"?
According to Computers and Intractability, Yes, it should, and it appears that problems of this kind violate the law of logical complement.
However, the answer is No.
Why? {The answer can be found here}
■Q2: Can the law of logical complement be violated?
■
No comments:
Post a Comment