P/NP

[fls]

Does anyone have suggestions for a book that provides a good review of the P/NP problem at a high-school/introductory college level?

Linda

[kmortis]

P/NP?

I take it you're not talking semiconductor materials?

[Jeff Corey]

Link http://www.claymath.org/millennium/P_vs_NP/

[69dodge]

You mean, enough to understand what the question is? Nobody knows the answer yet...

Sipser's textbook (http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/053494728X/ref=ed_oe_h/002-5796614-7588849) is good. There's a second edition out, so copies of the first edition aren't too expensive. Maybe it's too hard? Supposedly, it's "intended as an upper-level undergraduate or introductory graduate text in computer science theory," but I'm not sure it's really that hard.

Is it for someone who's actually in high school? Or do you just want an introductory text?

[fls]

Link http://www.claymath.org/millennium/P_vs_NP/

Thank you, but I don't think my son can get a 3000 word essay out of that. :)

Linda

[fls]

You mean, enough to understand what the question is? Nobody knows the answer yet...

Speaking of ways to get a million dollars.....

Sipser's textbook (http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/053494728X/ref=ed_oe_h/002-5796614-7588849) is good. There's a second edition out, so copies of the first edition aren't too expensive. Maybe it's too hard? Supposedly, it's "intended as an upper-level undergraduate or introductory graduate text in computer science theory," but I'm not sure it's really that hard.

Is it for someone who's actually in high school? Or do you just want an introductory text?

He's in high school. I suggested it as a topic for his extended essay (for the IB (http://www.ibo.org/) program). He's smart and he likes math. But he gave me a pretty blank look when I tried to explain it to him. :)

Linda

[mijopaalmc]

Speaking of ways to get a million dollars.....



He's in high school. I suggested it as a topic for his extended essay (for the IB (http://www.ibo.org/) program). He's smart and he likes math. But he gave me a pretty blank look when I tried to explain it to him. :)

Linda

I would suggest Chapter 3 of Keith Devlin's book The Millennium Problems (http://www.amazon.com/Millennium-Problems-Greatest-Unsolved-Mathematical/dp/0465017290). It is written for a lat audience; I didn't need to use any more than my basic calculus knowledge to understand any of the book and certainly not the P=NP chapter. Amazon also turns up The Millennium Prize Problems (http://www.amazon.com/Millennium-Prize-Problems-J-Carlson/dp/082183679X/ref=pd_lpo_k2_dp_k2a_1_txt/102-9774218-4936901), which looks like it might be more technical, but I don't know since I have never read it.

[Cuddles]

I think "The Code Book" by Simon Singh has a nice discussion of the P/NP problem.

[Soapy Sam]

OK- I'm an idiot. I can't count. I don't believe in complex numbers and I have doubts about real ones.
I KNOW you domeheads are taunting me.

So what in tarnation is the P&P problem?

ETA- In short, easy to read words, please.

[PogoPedant]

Blah.

I tried to explain the difference between P and NP, but it became hideously complicated. Sorry, Sam, I don't think I understand the field well enough yet...

[69dodge]

Can a computer quickly solve from scratch any problem the solution to which it could quickly recognize if it saw it?

(Along with suitably technical definitions of "computer", "quickly", "problem", and "solution".)

[roger]

Soapy,

It's a measure of how long it takes to solve a problem with a computer. Not a measure in an exact number (3.5 milliseconds, 2 million years), but by what kind of mathematical equation we need to use to express it.

Examples:

a) adding two numbers

Here the answer is constant time. For any computer, it takes a fixed time to add two numbers. Your computer may be twice as fast as mine, but it's still a constant. Your's may take 10ns, and mine takes 20ns.

Big deal you say. But let's see where this theory gets interesting by looking at different problems.

b) Find the sum of a row of numbers

this is a "linear" problem. Meaning if you have 10 numbers, it'll take 9 operations to find the solution. If you have 1000 numbers, it'll take 999 operations. As the problem gets bigger (more numbers to add), the time to solve the problem gets bigger by the same amount. If your problem set doubles, buy a second computer and you will be done in the same amount of time.

c) traveling saleman problem. This problem is non-polynomial. Don't worry if you don't understand that math term. In essense, what this means is the time to find the problem expands exponentially (or even more) as you add to the size of the problem.

Huh? Okay, the traveling saleman problem is easily stated. Given a bunch of cities and roads connecting them, find a route for the saleman so she can visit each city once while driving the shortest distance possible.

If there are 2 cities, finding the solution is trivial. Look at all roads connecting them (say an interstate and a country road), and choose the shortest one.

If there are 3 cities, it gets harder. You have too look at a lot more roads and route choices to figure out the shortest path.

By the time you have 10 cities, the problem takes a VERY long time to find a solution.

The times end up looking something like this (any computer scienteist will dispute the numbers; I made the numbers nice and uniform to give you the gist of the idea):

2 cities : 1 second
3 cities : 10 seconds
4 cities : 100 seconds
5 cities : 1000 seconds
6 cities : 10000 seconds
7 cities : 100000 seconds

Okay, the numbers don't explode quite that quickly, but it doesn't matter. You can see that just by adding a few more cities to the problem, the finding the solution quickly becomes impossible.

Now, the traveling salesperson problem may sound irrelevant, but it is actually very pertinent. Imagine routing jets, laying out printed board circuits, packing a shipping container, etc. All these are basically the traveling salesman problem in different clothes.

To put it in perspective: a typical NP problem requires more than the age of the universe to find an answer with a computer for a normal sized problem!

----------
Now, there is a lot of research on this issue, as you might imagine, on finding an efficient way to solve these problems. For example, there is an important subset of these problems called NP-complete (don't worry about why it is called that). We don't know if these problems are NP or not, but they probably are. Certainly our best efforts to program them so far are NP. But, there is an outside chance that we can find a P way to solve them - i.e. maybe a linear way. Finding this answer is literally worth billions, even trillions to industry.

But, most active research goes to finding other ways to finding a solution. Okay, we can't find the perfect answer for the salesman in the time remaining in the universe. How long does it take us to find a less than perfect, but still good solution? Well, given we are sending saleman around the world, and routing jets, etc., you might guess it doesn't take very long. And, it doesn't. We use heuristics to find less than perfect, but still pretty good solutions to these intractable problems. So, the shipping container might not be perfectly packed when put to sea, but it is 99% full, and that is enough for the shipping company to turn a profit. If it ran a computer simulation for 1million years it might fill that extra 1%, but I'm sure you can see the market inefficiency of that.

-----
ETA:
If you know high school alegbra, this will help:

Constant
time = c

linear
time = n (where n is the size of the problem set )

polynomial
time = cn^2 + dn + e

exponential
time = c^n

Our computers can handle polynomial problems (P) but not nonpolynomial problems (NP) like exponential problems. There are many kinds of NP problems; exponential is just one example.

[roger]

fls,

This seems like a difficult essay problem for a HS student. However, a great book for that aged student would be Godel, Escher, Bach. There is a lot more in that book than P/NP, and it probably isn't a good go-to book to just write an essay. But if they stick with the book cover to cover, they will end up with an education in computer science, cognitive science, snumber theory, some classical music, and many other things. It takes some thinking, but the writing and ideas are very accessible to a bright HS student.

[drkitten]

To put it in perspective: a typical NP problem requires more than the age of the universe to find an answer with a computer for a normal sized problem!

Minor terminological point -- or perhaps not quite so minor.

NP does not stand for "non-polynomial." That's one of the major sources of confusion on this question.

NP stands for "nondeterministic polynomial." The actual definition of NP (and of NP-complete) is quite difficult and technical, which is one reason that I'm not sure that this is appropriate for a high school student.

But what it really boils down to is not the difficult of solving a problem. There are lots of problems that are known to take lots and lots of time to solve, for whatever reason. There are some problems that are known to be so difficult, that even if I tell you the right answer, it takes a lot of time for you to confirm that I'm right.

Class NP is special. Class NP is the problems that it might take you a long time to solve yourself, but that if I tell you a purported answer, you can confirm fairly quickly that my answer is or is not correct. As a simple analogy -- if I hand you a zillion-piece jigsaw puzzle and ask you to solve it, that will take you a long time. But if I take you into a room and show you a jigsaw puzzle that's already solved, you can recognize at a glance that my solution is correct.

One would think that it would be easier to check a solution than to come up with one from scratch. But, in fact, that's exactly what we can't prove. Class P are the problems that we can solve quickly. Class NP are the problems that we can check quickly. And the question is whether or not there are any problems that we can provably check more quickly than we can solve. And the answer to that is -- we don't know. It seems plausible, but "plausible" doesn't cut much ice in mathematics.

[slyjoe]

And that is why the proof is worth a million dollars! :)

[fls]

I think "The Code Book" by Simon Singh has a nice discussion of the P/NP problem.

Thank you Cuddles. And thank you 69dodge for suggesting Sipser (I didn't actually say that in my reply).

Linda

[roger]

Minor terminological point -- or perhaps not quite so minor.

NP does not stand for "non-polynomial." That's one of the major sources of confusion on this question.Arrg, you are quite correct, and it is not minor. Thank you.

[fls]

I would suggest Chapter 3 of Keith Devlin's book The Millennium Problems (http://www.amazon.com/Millennium-Problems-Greatest-Unsolved-Mathematical/dp/0465017290). It is written for a lat audience; I didn't need to use any more than my basic calculus knowledge to understand any of the book and certainly not the P=NP chapter. Amazon also turns up The Millennium Prize Problems (http://www.amazon.com/Millennium-Prize-Problems-J-Carlson/dp/082183679X/ref=pd_lpo_k2_dp_k2a_1_txt/102-9774218-4936901), which looks like it might be more technical, but I don't know since I have never read it.

I know it's supposed to be written for a lay audience, but I think someone without some background knowledge would have trouble understanding Devlin.

Linda

[fls]

fls,

This seems like a difficult essay problem for a HS student. However, a great book for that aged student would be Godel, Escher, Bach. There is a lot more in that book than P/NP, and it probably isn't a good go-to book to just write an essay. But if they stick with the book cover to cover, they will end up with an education in computer science, cognitive science, snumber theory, some classical music, and many other things. It takes some thinking, but the writing and ideas are very accessible to a bright HS student.

That was my first thought. And I will recommend that he reads the book anyway. But I figured the size would scare him off. :)

Linda

[fls]

NP stands for "nondeterministic polynomial." The actual definition of NP (and of NP-complete) is quite difficult and technical, which is one reason that I'm not sure that this is appropriate for a high school student.

I agree that it would be difficult for a high school student to have a detailed understanding. I suggested an essay about the implications of finding a solution. I think a general understanding of the problem would be sufficient for that purpose, rather than an understanding of the mathematics it would require to form the proof.

I hope I'm not off-base on this.

Linda

[tracer]

Now, there is a lot of research on this issue, as you might imagine, on finding an efficient way to solve these problems. For example, there is an important subset of these problems called NP-complete (don't worry about why it is called that). We don't know if these problems are NP or not, but they probably are. Certainly our best efforts to program them so far are NP. But, there is an outside chance that we can find a P way to solve them - i.e. maybe a linear way. Finding this answer is literally worth billions, even trillions to industry.
I'd just like to add my two cents here:

The reason it would be worth so much to find a P solution to an NP-complete problem is that all NP-complete problems are interconvertible. That is to say, I can turn any one NP-complete problem into any other NP-complete problem. If somebody hands me a Travelling Salesman problem, I can turn it into a Binomial Expansion problem. If someone hands me a Binomial Expansion problem, I can turn it into a prime number modulus search problem. Et cetera.

So, if we find one P solution to any one of these NP-complete problems, we've found a P solution to them all.

[mijopaalmc]

I know it's supposed to be written for a lay audience, but I think someone without some background knowledge would have trouble understanding Devlin.

Linda

I'm not sure what kind of mathematical background your son has (I was assuming that the IB curriculum includes calculus much like the the AP curriculum), but I was able to understand Devlin's book with only three semesters of college calculus. I did not really even need to use that knowledge to understand the "P vs. NP" chapter. I would definitely recommend at least checking out Devlin's book, if your local library has it.

You might also want to see if there is any popular mathematical literature on, most likely book-length treatments of, P vs NP. I know there are many more such book on some of the other Millennium Problems, for instance the Riemann Hypothesis.

[drkitten]

I'm not sure what kind of mathematical background your son has (I was assuming that the IB curriculum includes calculus much like the the AP curriculum), but I was able to understand Devlin's book with only three semesters of college calculus.

In my experience/opinion, it's not so much needing calculus per se as that infinitely abusable "mathematical maturity." Understanding a nondeterministic Turing machine isn't that hard in terms of content; it's just an application of discrete mathematics. Understanding the idea of polynomial functions (and the idea of a polynomial-time reduction) doesn't take more than high school algebra.

.... and the ability to trace through some very sophisticated chains of definitions and reasons. Go ahead, tell me what's "universal" about a UTM.....

... in words that don't presume familiarity with Cantor, Frege, Russell, and Godel.

[roger]

I'd just like to add my two cents here:

The reason it would be worth so much to find a P solution to an NP-complete problem is that all NP-complete problems are interconvertible. That is to say, I can turn any one NP-complete problem into any other NP-complete problem. If somebody hands me a Travelling Salesman problem, I can turn it into a Binomial Expansion problem. If someone hands me a Binomial Expansion problem, I can turn it into a prime number modulus search problem. Et cetera.Yes, I remember having to prove that one NP problem was equivalent to another in exams oh so long ago, though I now no longer remember the proof mechanism; I just wasn't sure how much that would help Soapy understand P/NP. There is a large universe of problems which are not provably P, NP-Complete are interesting because of the property you mention. However, if I was a betting man, I'd bet that we never find an efficient solution to NP-Complete.

[69dodge]

Go ahead, tell me what's "universal" about a UTM.....

... in words that don't presume familiarity with Cantor, Frege, Russell, and Godel.


A universal Turing machine can simulate any Turing machine.

Did you have something else in mind?

[drkitten]

A universal Turing machine can simulate any Turing machine.

Did you have something else in mind?

Yes. An explanation of how.

[Myriad]

A nondeterministic computer might not be that hard to understand, in principle. Think of it as a computer that every time a normal computer would have to follow a loop in its program to test each of a number of possibilities (such as, which city the travelling salesman should go to first), can instead tell in one step which (if any) of the possibilities will lead to a solution. No such computer actually exists; it's a mathematical concept. (It's not necessary for one to exist, in order for computing theory to pose, and sometimes answer, well-defined questions about the capabilities of such a computer, if it did exist.)

One way to visualize how a nondeterministic computer might operate is to imagine that the nondeterministic computer, whenever it must test multiple possible choices, can instantly create a bunch of copies of itself so that each copy only has to evaluate one of the choices. For NP complete problems like the travelling salesman problem, each copy ends up (usually) having to make more copies, for instance to try each possibility for the second city the salesman could visit. (For a typical problem, to actually complete this process, you'd end up generating far more "copies" of the computer than there are atoms in the universe.)

Another way to visualize it is to imagine that the nondeterministic computer can use mathematics that we haven't discovered yet, to be able to decide, each time the next part of a solution could be one of many possibilites, which of the possibilities must be chosen to eventually get to the correct solution, even though it hasn't figured out the whole solution yet and even though the parts of the solution appear to be interdependent.

I think the WOPr in the movie War Games might be a nondeterministic computer. When it's trying to figure out the secret launch code that the humans refuse to give it, it somehow figures out one digit at a time, and displays the "found" digits while all the others are still running through possibilities. Oddly (but perhaps expectedly, for a nondeterministic computer), it takes just as long to find the last digit as it did to find each of the first few, even though at that point there couldn't be more than a few dozen possibilities to check!

Some of the hoopla over "quantum computing" comes from the notion that a quantum computer might be able to operate like a nondeterministic computer in some respects. Instead of making multiple copies of itself, it supposedly creates a superimposition of all the possible solutions that it's working on, and computes the next steps for all the possible solutions simultaneously.

To say that a certain problem could be solved by a nondeterministic computer in a relatively small number of steps is a highly precise (given more precise definitions of "nondeterministic computer" and "relatively small number of steps" than I've given here) and technical way of saying that it only takes a relatively small number of computations to test whether a proposed solution for the problem is valid. That's what makes the problem "NP."

To say a problem is NP-complete means, basically, that (1) it is NP, and (2) it is computationally equivalent to all other NP-complete problems, such that any way to solve it using a normal computer using a number of steps that does not increase exponentially with the number of elements (such as cities to visit) in the problem, could be converted into methods for solving all other known NP-complete problems in faster than exponential time too.

P ?= NP is the question, "Does such an algorithm exist?" (I'm not sure whether, to win the millennial prize, it's enough to prove a solution exists, or if you have to actually find one.)

Respectfully,
Myriad

[Sleepy]

But, there is an outside chance that we can find a P way to solve them - i.e. maybe a linear way. Finding this answer is literally worth billions, even trillions to industry.


Just a minor nitpick/expansion here regarding the "i.e. maybe linear" part. While linear or constant is ideal, even a high order polynomial time algorithm is much better than any exponential time algorithm. In fact many algorithms in use today are n^3 or worse... and I wouldn't flinch at running n^2 algorithms on a few million items even on my old pc here...

Every professor I've asked hopes for that "outside chance" you mention but the consensus seems to be P != NP.

Anyway, I have a hunch we'll probably invent an actual nondeterministic computer :cool: before we learn whether P = NP or not. :confused:

[cyborg]

Yes. An explanation of how.

The simplest explanation would be that the Turing machine's operation can be described by another Turing machine.

Essentially it means you can write interpreters in a Turing machine.

[69dodge]

Yes. An explanation of how.


Oh. That's harder. :D

Then again, programming a Turing machine to do anything is fairly hard.

The assembliest of assembly languages...

Turing's 1936 paper (http://www.abelard.org/turpap2/tp2-ie.asp) is available online, if anyone's interested. Section 9 is well worth reading. Not too technical, and explains his motivation for defining Turing machines the way he did.

More stuff about Turing. (http://www.turing.org.uk/turing/scrapbook/machine.html) Says there, in the middle of the page, that an original copy of the journal volume containing the paper is estimated at $15,000 - $20,000. Wow. At the NY Public Library some years ago, they let me borrow it to make a copy, no questions asked. They probably shouldn't have. It was kind of falling apart. Cracked yellowing pages, etc. Obviously I wasn't the only person to have copied that particular paper. Very famous paper. It was pretty funny, though. Just those few pages were a mess. The rest of the volume was pristine.

[fls]

I'm not sure what kind of mathematical background your son has (I was assuming that the IB curriculum includes calculus much like the the AP curriculum), but I was able to understand Devlin's book with only three semesters of college calculus. I did not really even need to use that knowledge to understand the "P vs. NP" chapter. I would definitely recommend at least checking out Devlin's book, if your local library has it.

I have the book. It just strikes me that Devlin's writing makes sense when you already have a mathematical framework in place, but would be confusing to someone who doesn't have a feel for the big picture. It seems a bit haphazard and uneven, compared to the writings of someone like Hofstadter or Feynman.

I realize this criticism is unfair, since it would be hard for it to be any different when trying to reduce decades of complicated mathematical reasoning to a single book chapter. And I'm not opposed to the suggestion, just wondering what else is out there for some who is naive relative to me.

Linda

[Soapy Sam]

It was probably the UV from all the photocopying that had yellowed the page?

Thanks for the explanations , people. It's pearls before swine in my case, you appreciate, but we must always remember the potentially brighter lurkers.
If all NP type problems are equivalent, (for a given meaning of equivalence), presumably there must be some similarity between the solutions as a class?
If any solution is known , by some accretionary / evolutionary process, does this not suggest a way to tackle others?
What often astonishes me (I have a low astonishment threshold) is the way a rock , being thrown, manages to land in the absolute spot decreed by the very trajectory it followed- almost as though the two were causally connected! - without doing any calculation whatever.
A photon , presumably, may go by every possible route, but I never knew a rock to do so. Or a salesman.
Similarly, the actual solution to a travelling salesman problem of moderate complexity will be a fairly simple line. Why is it so easy for the rock, yet so hard to calculate? Are we missing something fundamental?
(This is NOT a rhetorical question, just an expression of a deep seated sense of unease;- but this is my traditional response to most mathematical issues.)

[MRC_Hans]

Interesting. If you will allow me a slight derail, I think that some NP problems may have specific solutions, so it may be that the real crunch is to find a universal algorithm.

Somebody mentioned routing printed circuit boards (essentially identical to the travelling salesman problem). This happens to be one of my areas of expertise, and here there exists computer programs that can make solutions in a finite time. The method here is a combination of a low level of trying all possibilities (for two nodes) and iteration. In this way, an algorithm is created that can converge on an ideal solution (in many of these problems there will be more than one solution). You can then decide how long you will let the process run, and thus how good an approximation you will get to an ideal solution.

Now throw in a finite resolution to the artwork (or in the travelling salesman problem, decide that you will only calculate whole miles), and the process will terminate naturally (by two subsequent iterations reaching the same solution).

OK, end of derail ;)

Hans

[roger]

It was probably the UV from all the photocopying that had yellowed the page?

Thanks for the explanations , people. It's pearls before swine in my case, you appreciate, but we must always remember the potentially brighter lurkers.
If all NP type problems are equivalent, (for a given meaning of equivalence), presumably there must be some similarity between the solutions as a class?

All are not equivelent. This is true for NP-Complete problems, and the case is even strong than you state it. If we can solve one, we can automatically solve them all. That's why it is such a topic of research.

However, there are many different classes of non-P. NP, NP-complete, NP-hard, NL, RE-complete, etc., etc. There are hundreds.

There are often no relations between these. Consider one problem whose complexity is 2^n. That sounds horrible, and it is. But, compare it to a n^n^n^n problem, and 2^n sounds downright inviting. Any possible speedup to a 2^n problem almost certainly is not going to have an appreciable affect on a n^n^n^n problem, even if it could be applied.


Your rock question is not naive at all, in my view. Important classes entails asking what we can do with parallel machines. For example, P-complete entails P problems which reduced to logrithmic complexity on parallel computers. A way of thinking about the rock is it has a gazillion parallel computers, one for each position in space, computing the rock's position in the next instant - is it in this space position, or not? As it turns out (unsurprisingly), the solution can be found by this manner.

However, as I'm sure DrKitten and others are screaming as they read this, we don't need a gabillion processors to calculate the position of the rock - a hand calculator will do. But, you chose a slightly incorrect physical example - better examples would be "how does the wind know how to flow smoothly around a plane wing" or something like that. A single computer takes forever to do fluid flow computations, a network of parallel computers can reduce the time tremendously.

Again, that is a simplification - some problems react to parallelism well, some not at all, and a lot get only some benefits. It's a very active research topic, driven many times by your question - how are things 'calculated' in the real world. There's a lot of complex math behind it, which is better left to DrKitten to explain, but trust me your question was not bad at all.

For example, I participate in the folding@home program. This is run by Stanford, and is dedicated to figuring out how proteins fold. This is vastly computationally intensive, and so they offload the computing to a bunch of home computers, just like seti@home. However, we really still don't know how to compute folding in any short time period - proteins fold in a blink of an eye (a few milliseconds to a second on average), yet even with parallelism the effort to compute a fold for even a tiny protein is vast. Researchers are putting a lot of work into figuring out how we can improve the algorithms. When they do, it is quite possible that the results will be beneficial to many other areas of computation.

[Dr Adequate]

What often astonishes me (I have a low astonishment threshold) is the way a rock , being thrown, manages to land in the absolute spot decreed by the very trajectory it followed- almost as though the two were causally connected! - without doing any calculation whatever. "Nature integrates empirically" --- Albert Einstein.

[Schneibster]

The interesting thing about most NP problems is that they have more than one solution. Good examples of this are automated printed circuit board trace routing and the related problem of automated long-distance telephone call routing. Another related problem is packet routing on the Internet.

What mathematicians want, though, is a terminating procedure for finding all the correct solutions (not a correct solution) for NP problems without having to iterate over every possible solution.

[69dodge]

It was probably the UV from all the photocopying that had yellowed the page?


Can photocopying do that?

Anyway, I wasn't very clear. I think the whole thing was yellow and brittle. But only some of the pages were falling out or had pieces broken off, because they were the ones that had been handled a lot over the years.

If all NP type problems are equivalent, (for a given meaning of equivalence), presumably there must be some similarity between the solutions as a class?
If any solution is known , by some accretionary / evolutionary process, does this not suggest a way to tackle others?


Yes, all NP-complete problems are equivalent to each other in a certain sense, and (some) similarities between them are understood. The way two problem are demonstrated to be equivalent is generally (always?) by showing explicitly how to solve one quickly, given a method of solving the other quickly. But we don't know of a quick method for any of them at the moment, and there might not be any quick method possible.

What often astonishes me (I have a low astonishment threshold) is the way a rock , being thrown, manages to land in the absolute spot decreed by the very trajectory it followed- almost as though the two were causally connected! - without doing any calculation whatever.
A photon , presumably, may go by every possible route, but I never knew a rock to do so. Or a salesman.
Similarly, the actual solution to a travelling salesman problem of moderate complexity will be a fairly simple line. Why is it so easy for the rock, yet so hard to calculate? Are we missing something fundamental?
(This is NOT a rhetorical question, just an expression of a deep seated sense of unease;- but this is my traditional response to most mathematical issues.)


As roger said, it is easy to calculate the path of a rock. It's a parabola.

The travelling salesman problem is much harder (as far as we know). The solution will be a fairly simple line, once you have it. But how do you get it? There are so many different possible fairly simple lines it could a priori be.

[69dodge]

What mathematicians want, though, is a terminating procedure for finding all the correct solutions (not a correct solution) for NP problems without having to iterate over every possible solution.


Where did you get this from?

(It doesn't sound right. But it's hard to say for sure without more details.)

[Schneibster]

From experience with computer algorithms that can provide a solution to certain classes of NP problems, notably those I referred to above. One class of such solutions is called the "Lee flood algorithm." Interestingly, despite its applicability (and despite the fact that the design of RIP incorporates features that amount to its implementation piecemeal in the infrastructure of the 'Net), few if any references emerge in a search for it. The algorithm was originally developed for AT&T, for use in routing telephone calls across its network of long-distance lines and through offices.

ETA: Lee flood is also known (apparently more commonly) as "shortest-path first" algorithms, when used in network routing. You may find this (http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/routing.htm) interesting; search on "flood."

[mijopaalmc]

I have the book. It just strikes me that Devlin's writing makes sense when you already have a mathematical framework in place, but would be confusing to someone who doesn't have a feel for the big picture. It seems a bit haphazard and uneven, compared to the writings of someone like Hofstadter or Feynman.

I realize this criticism is unfair, since it would be hard for it to be any different when trying to reduce decades of complicated mathematical reasoning to a single book chapter. And I'm not opposed to the suggestion, just wondering what else is out there for some who is naive relative to me.

Linda

Sorry, I didn't mean to push a book you already knew something about.:)

[Tez]

The interesting thing about most NP problems is that they have more than one solution. Good examples of this are automated printed circuit board trace routing and the related problem of automated long-distance telephone call routing. Another related problem is packet routing on the Internet.

What mathematicians want, though, is a terminating procedure for finding all the correct solutions (not a correct solution) for NP problems without having to iterate over every possible solution.

Not really - the hard instances of NP problems are those with very small numbers of solutions. There is actually a theorem that "NP is as easy as detecting unique solutions" (its the title of the paper, you can google it).

The amazing thing is that the conjecture P~=NP essentially asserts the difficulty of proving itself. See e.g. half way through this for a simple discussion:

http://www.lepp.cornell.edu/spr/2006-02/msg0073087.html

[Complexity]

What mathematicians want, though, is a terminating procedure for finding all the correct solutions (not a correct solution) for NP problems without having to iterate over every possible solution.


Mathematicians may want such an algorithm, but that is not what NP-completeness is all about.

Finding one solution is sufficient.

For example, my favorite NP-complete problem is k-Clique Exists, which asks whether a complete subgraph of size k exists in a graph. The problem requires only a single solution. Indeed, if you can design a polynomial-time worst-case algorithm to solve this (or any other NP-complete problem), you will have proven that P = NP. This is exactly what I am trying to do.

People are interested in many variants on this problem: e.g. list all complete subgraphs of size k, list all maximal cliques of a graph (cliques that are not subgraphs of other maximal cliques).

I've got an algorithm for the maximal cliques problem and have been attacking the k-Clique Exists problem for 17 years, resulting in six new algorithms for it. One of the k-Clique Exists algorithms is quite promising.

I'm one of those who suspect that P = NP. Whether or not this is true, we need much better algorithms for NP-complete problems.

[Beleth]

I tried to explain the difference between P and NP, but it became hideously complicated.
As a teacher of a co-worker of mine once said:

"To understand the concept of NP, first you must understand P-ness."

It's funnier if you say it out loud.

[Soapy Sam]

Can photocopying do that?

Don't see why not. If not, it's widely believed by librarians and art curators that it can. I guess the question is - what frequencies of light does a photocopier emit?

As roger said, it is easy to calculate the path of a rock. It's a parabola.
Relative to the planet / thrower, yes.
But how does the rock know that? And does it know it before it is thrown and and every point in it's flight? Where in a lump of basalt is the information encoded which says it's not orbiting Jupiter? Or is that encoded in spacetime? And if so, is the salesman's route a property of his sales target policy or of spacetime? Before starting a calculation, are we sure what we are looking for?

The travelling salesman problem is much harder (as far as we know). The solution will be a fairly simple line, once you have it. But how do you get it? There are so many different possible fairly simple lines it could a priori be.
So- does the line exist in potentia in reality? Or only in our imaginations?
Which is essentially the same thing I occasionally wonder about numbers.

[Tez]

Here are some of Scott Aaronson's blog writings which give an overview of the problem in a casual way. Somewhere he has a list of the "godlike" powers P=NP would imply, but I haven't managed to track it down.


http://scottaaronson.com/blog/?p=152

http://scottaaronson.com/blog/?p=122

A fun paper of his he mentions:

http://arxiv.org/abs/quant-ph/0502072

[cyborg]

But how does the rock know that?

The rock doesn't. It doesn't need to. The parabola is just what we observe when the rock behaves as it does. It is not actively seeking to follow it. You are thinking about this back-to-front.

[Schneibster]

Not really - the hard instances of NP problems are those with very small numbers of solutions. There is actually a theorem that "NP is as easy as detecting unique solutions" (its the title of the paper, you can google it).Well, first, while there is a theorem in there, there is considerable controversy over whether it shows it for all NP-complete problems, which is the implicit claim of the title. Second, the paper is about reduction of the possible solution set without eliminating any of the actual solutions- in other words, finding all the solutions, not just one. Which is what I said. So I'm not sure why you said "not really."

The reference is interesting, and I thank you for it.

The amazing thing is that the conjecture P~=NP essentially asserts the difficulty of proving itself. See e.g. half way through this for a simple discussion:

http://www.lepp.cornell.edu/spr/2006-02/msg0073087.htmlInteresting. Thanks for that one, too.

[Tief]

Unrelated to the topic, I seem to have a mental block when it comes to figuring this out -

What does 'ETA' stand for?:o

[Wavicle]

For example, my favorite NP-complete problem is k-Clique Exists, which asks whether a complete subgraph of size k exists in a graph. The problem requires only a single solution. Indeed, if you can design a polynomial-time worst-case algorithm to solve this (or any other NP-complete problem), you will have proven that P = NP. This is exactly what I am trying to do.


Hey that's pretty neat. So I have a question (sadly my university had woefully lacking coverage of P and NP): it's fairly obvious that this k-Clique problem has a linear time verification of solution. But it is not obvious (to me at least) that a traveling salesman problem has a linear time verification of solution. You can verify that a proposed solution will take the salesman to every city in linear time, but it isn't clear to me that you can easily verify that a proposed solution is the smallest solution without looking at all the other solutions and comparing.

So, what am I missing here?

ETA: Now that I've thought about it a little more, I think maybe verifying the solution to the k-Clique problem is quadratic. Still better than what it seems like you'd have to do for traveling salesman.

[drkitten]

Hey that's pretty neat. So I have a question (sadly my university had woefully lacking coverage of P and NP): it's fairly obvious that this k-Clique problem has a linear time verification of solution. But it is not obvious (to me at least) that a traveling salesman problem has a linear time verification of solution. You can verify that a proposed solution will take the salesman to every city in linear time, but it isn't clear to me that you can easily verify that a proposed solution is the smallest solution without looking at all the other solutions and comparing.

So, what am I missing here?

Some technical points here.

The usual formulation of class P does not permit numeric problems. So the formal definition of the Travelling Salesman problem is not "what is the shortest route for the travelling salesman," but "for a specified value B, is there a raote that is shorter than B?" Obviously, if you can answer this questison in time polynomial in N, you can answer the optimization in time polynomial in N times the log of the maximum possible answer (via binary search).

And, of course, it's possible to verify that the proposed solution is shorter than B in polynomial time -- linear, probably, unless you have some wierd data storage method.

It's a fairly easy proof that the decision problem is no easierr than the corresponding optimization problem -- and in many cases, including travelling salesman, it's easy to prove that they're equally difficult. So the minor technical restriction doesn't actually hurt at all....

[Soapy Sam]

Tief-
"Edited to add".
"Estimated time of arrival"
"Extremely trivial abbreviation".

[Wavicle]

Some technical points here.

The usual formulation of class P does not permit numeric problems. So the formal definition of the Travelling Salesman problem is not "what is the shortest route for the travelling salesman," but "for a specified value B, is there a raote that is shorter than B?" Obviously, if you can answer this questison in time polynomial in N, you can answer the optimization in time polynomial in N times the log of the maximum possible answer (via binary search).

Okay, after a bit of googling along this vein I think I have an answer. My definition of the traveling salesman problem was essentially correct (Wolfram defines the problem as "the most efficient Hamiltonian circuit a salesman can take through each of n cities") but is not NP-Complete, it is NP-Hard. Your definition is what wikipedia calls the "decision problem" version which is NP-Complete. And now it makes sense that you could transform the decision problem TSP to k-Clique, and my fragile grasp of P and NP continues unshattered.

I guess which form of the problem you are going to consider depends on which context you are looking.