I wish I had something more to say than that this is a beautiful essay. As a mathematician, I know that communicating an understanding of what I do requires that I communicate subtleties far finer than non-technical language seems to allow (non-ambiguously). Much of the (very very little) training that mathematicians receive in popular communication teaches us to simplify or elide these distinctions; but it is nice to hear a voice warning that over-simplification, that achieves apparent comprehension at the expense of later profound misunderstanding, can lie at the end of that slippery slope.
At the end of the day, language is a set of auditory approximations that allow us to share ideas that we have in our minds with others. As a philosopher, I interpret this as our inability share a complete thought, with all its intricacies and nuance, with another person. In many cases, this means it can be more accurate to imprecisely share a thought than to attempt to do so with precision - the imprecise thought doesn't paint the whole picture, but it leaves fewer unimportant details (at least in the opinion of the speaker) up for interpretation.
This is exactly why the ancient Greeks viewed philosophy and rhetoric as two sides of the same coin. This is also why I feel most engineers need better written / verbal communication skills: "soft skills" are all about when to be verbose / concise, what tone or communication methods to use in what situation, and how to read your audience to know what level of communication they need to hear.
The story from the article tells me a good deal about the interviewer and the interviewee: the interviewer has the presence of mind to understand his meaning was not getting through and how to keep that from happening in the future. The interviewee should have asked more clarifying questions if he did not understand. Misunderstanding is a two-way street; and at least in an interview, it can be helpful to see how someone reacts to a question they don't fully understand.
Yes; the sheer size of the search space isn't what makes the problem hard.
Here is an obvious difference:
In sorting, we have locally correct solutions in that given any two distinct elements a, b out of the N, we know whether a is to the left or to the right of b in the final order. Moreover, for a given a, we can find, in linear time, the smallest b which is greater than a: a's successor in the sorted order. Thus sorting is no worse than quadratic. Also, we can examine any permutation of the N items and tell in one pass whether or not it is in sorted order. So recognizing solutions to the sorting problem is linear.
Given any two cities, a and b out of N, we do not know which one is visited first in the shortest path, and we certainly don't know what a's successor will be in the solution. Even verifying a solution to the problem (Is this sequence of cities the shortest path?) cannot be done in polynomial time.
So, yes, the mere fact that there are N! orders to search through is by itself unconvincing about the hardness of the problem.
Lectures on it would be easy if that were the case: Good morning everyone; today we discuss a class of so-called "NP hard" problems, which occur whenever there is a combinatorial explosion in a search space. :)
> Given any two cities, a and b out of N, we do not know which one is visited first in the shortest path, and we certainly don't know what a's successor will be in the solution. Even verifying a solution to the problem (Is this sequence of cities the shortest path?) cannot be done in polynomial time.
Usually, the problem is simplified to a threshold test, like: Does this tour have path length < X? These kind of problems are equivalently difficult to produce solutions for in the general case, but are straightforward to verify.
That's true; "hard to verify" isn't the good criterion either for a succinct distinction; all kinds of hard problems are easy to verify in poly time, including a modified version of this one.
The most succinct informal description I have for NP-complete problems is lack of optimal substructure; that is, given a solution to part of the problem, it's possible for that to not help at all for solving the whole problem.
For Traveling Salesman, this means that given the best tour for an N-city graph, the best tour for the same graph augmented by a single vertex could be entirely different.
And this is easy to then contrast with, say, sorting, to counter the earlier objection.
We can split the set into two, sort the two parts individually and then trivially merge the results. We cannot split the cities into two, solve the traveling salesman problem, and then easily merge the results.
And adding a new element to a sorted list is just a linear insertion.
> Even verifying a solution to the problem (Is this sequence of cities the shortest path?) cannot be done in polynomial time.
This is a pretty funny claim to see made about one of the most famous NP-complete problems there is. As thelema314 points out, the usual certificate verifies "is this path shorter than a threshold?".
I've concluded that I can't just use these example problems to explain things to non-programmers without thinking about them and deciding whether they are targeted specifically at computer scientists or at the public.
For instance: the Byzantine generals problem can be understood by the public as well as scientists: it doesn't seem all that contrived, just simplified. However, the dining philosophers problem doesn't usually go down very well: it seems contrived rather than simplified. The response I usually get is something like: give them more chopsticks, DONE.
On that note, I really wish I had some lucid way of explaining that these model problems are whimsical ways of conveying the essence of a difficult abstract problem, rather than actually representing an actual concrete problem.
11 comments
[ 5.8 ms ] story [ 37.2 ms ] threadThis is exactly why the ancient Greeks viewed philosophy and rhetoric as two sides of the same coin. This is also why I feel most engineers need better written / verbal communication skills: "soft skills" are all about when to be verbose / concise, what tone or communication methods to use in what situation, and how to read your audience to know what level of communication they need to hear.
The story from the article tells me a good deal about the interviewer and the interviewee: the interviewer has the presence of mind to understand his meaning was not getting through and how to keep that from happening in the future. The interviewee should have asked more clarifying questions if he did not understand. Misunderstanding is a two-way street; and at least in an interview, it can be helpful to see how someone reacts to a question they don't fully understand.
Here is an obvious difference:
In sorting, we have locally correct solutions in that given any two distinct elements a, b out of the N, we know whether a is to the left or to the right of b in the final order. Moreover, for a given a, we can find, in linear time, the smallest b which is greater than a: a's successor in the sorted order. Thus sorting is no worse than quadratic. Also, we can examine any permutation of the N items and tell in one pass whether or not it is in sorted order. So recognizing solutions to the sorting problem is linear.
Given any two cities, a and b out of N, we do not know which one is visited first in the shortest path, and we certainly don't know what a's successor will be in the solution. Even verifying a solution to the problem (Is this sequence of cities the shortest path?) cannot be done in polynomial time.
So, yes, the mere fact that there are N! orders to search through is by itself unconvincing about the hardness of the problem.
Lectures on it would be easy if that were the case: Good morning everyone; today we discuss a class of so-called "NP hard" problems, which occur whenever there is a combinatorial explosion in a search space. :)
Usually, the problem is simplified to a threshold test, like: Does this tour have path length < X? These kind of problems are equivalently difficult to produce solutions for in the general case, but are straightforward to verify.
For Traveling Salesman, this means that given the best tour for an N-city graph, the best tour for the same graph augmented by a single vertex could be entirely different.
And this is easy to then contrast with, say, sorting, to counter the earlier objection.
We can split the set into two, sort the two parts individually and then trivially merge the results. We cannot split the cities into two, solve the traveling salesman problem, and then easily merge the results.
And adding a new element to a sorted list is just a linear insertion.
This is a pretty funny claim to see made about one of the most famous NP-complete problems there is. As thelema314 points out, the usual certificate verifies "is this path shorter than a threshold?".
For instance: the Byzantine generals problem can be understood by the public as well as scientists: it doesn't seem all that contrived, just simplified. However, the dining philosophers problem doesn't usually go down very well: it seems contrived rather than simplified. The response I usually get is something like: give them more chopsticks, DONE.
On that note, I really wish I had some lucid way of explaining that these model problems are whimsical ways of conveying the essence of a difficult abstract problem, rather than actually representing an actual concrete problem.