Author |
Topic: P vs NP debate (Read 833 times) |
|
amichail
Senior Riddler
Posts: 450
|
 |
P vs NP debate
« on: Oct 18th, 2006, 4:19am » |
 Quote  Modify
|
I am baffled as to why theoreticians spend so much time debating whether it is likely that P != NP:
http://weblog.fortnow.com/2006/10/scott-and-p-versus-np.html
This seems like a completely pointless exercise to me. Why do it at all? If anything, majority opinion from such debates could delay resolution of the problem by decades.
I suppose that one might argue that looking for a lower bound requires similar considerations at some level as looking for an upper bound. So one would not be misled too badly by majority opinion. But this is not obvious to me.
Maybe the real reason for these debates is not so much that they will help resolve the issue in a direct way but rather that they will generate more interest in the field -- thus attracting more funding and students. So in a rather indirect sense, maybe these debates may help resolve the issue after all.
|
|
 IP Logged |
DropZap - a new kind of block elimination game
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
|
Re: P vs NP debate
« Reply #1 on: Oct 18th, 2006, 6:31pm » |
Quote Modify
|
This is because you don't understand theoreticians! To us (all mathematicians are theoreticians by default), it doesn't matter if the debate is pointless. For us the question itself IS the point. We view application much like a gourmand views defecation: an unavoidable consequence, but not at all the point of our occupation.
For nasty problems such a P vs NP, when no neat approach appears within sight, we are forced to debating our guesses with each other in order to show how smart we are.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
amichail
Senior Riddler
Posts: 450
|
|
Re: P vs NP debate
« Reply #2 on: Oct 19th, 2006, 12:40am » |
Quote Modify
|
on Oct 18th, 2006, 6:31pm, Icarus wrote:
For nasty problems such a P vs NP, when no neat approach appears within sight, we are forced to debating our guesses with each other in order to show how smart we are.
|
|
I don't see how pointless debate makes people look smart.
|
|
IP Logged |
DropZap - a new kind of block elimination game
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: P vs NP debate
« Reply #3 on: Oct 19th, 2006, 1:02am » |
Quote Modify
|
on Oct 19th, 2006, 12:40am, amichail wrote:| I don't see how pointless debate makes people look smart. |
|
But it's not pointless, the debate itself is the point. Even if a debate doesn't lead anywhere, you may still be able to construct good arguments. Debating is a cognitive skill you can hone simply by doing it, rather than applying it to an end.
It's like saying soccer practice is pointless, because any goals you score don't matter anyway, because you're not playing another team. But all the while you are honing your skills.
Sheer impossible problems are a good training area for thought, because that's all you have there.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
amichail
Senior Riddler
Posts: 450
|
|
Re: P vs NP debate
« Reply #4 on: Oct 19th, 2006, 1:07am » |
Quote Modify
|
on Oct 19th, 2006, 1:02am, towr wrote:
But it's not pointless, the debate itself is the point. Even if a debate doesn't lead anywhere, you may still be able to construct good arguments. Debating is a cognitive skill you can hone simply by doing it, rather than applying it to an end.
It's like saying soccer practice is pointless, because any goals you score don't matter anyway, because you're not playing another team. But all the while you are honing your skills.
Sheer impossible problems are a good training area for thought, because that's all you have there. |
|
These are not debates involving serious proof attempts. It's mostly just high level speculation.
Theory is different from most other fields in the sense that debate can be absolutely useless since ultimately proofs are not forgiving in any way.
|
| « Last Edit: Oct 19th, 2006, 1:08am by amichail » |
IP Logged |
DropZap - a new kind of block elimination game
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: P vs NP debate
« Reply #5 on: Oct 19th, 2006, 5:19am » |
Quote Modify
|
on Oct 19th, 2006, 1:07am, amichail wrote:
These are not debates involving serious proof attempts. It's mostly just high level speculation.
Theory is different from most other fields in the sense that debate can be absolutely useless since ultimately proofs are not forgiving in any way. |
|
On the other hand, even the least promising of speculative comments about the possible consequences of something being true or false might lead to a useful insight. How far from any obvious lines of attack did the eventual proof of Fermat's Last Theorem end up?
|
|
IP Logged |
|
|
|
amichail
Senior Riddler
Posts: 450
|
|
Re: P vs NP debate
« Reply #6 on: Oct 19th, 2006, 5:23am » |
Quote Modify
|
on Oct 19th, 2006, 5:19am, rmsgrey wrote:
On the other hand, even the least promising of speculative comments about the possible consequences of something being true or false might lead to a useful insight. |
|
Such speculative comments could be harmful as well. So the question is, how often is such debate helpful for difficult problems in theory?
|
|
IP Logged |
DropZap - a new kind of block elimination game
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: P vs NP debate
« Reply #7 on: Oct 19th, 2006, 5:36am » |
Quote Modify
|
on Oct 19th, 2006, 5:23am, amichail wrote:
Such speculative comments could be harmful as well. So the question is, how often is such debate helpful for difficult problems in theory?
|
|
If no-one's making any progress, then the amount of harm possible is pretty minimal.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: P vs NP debate
« Reply #8 on: Oct 19th, 2006, 3:39pm » |
Quote Modify
|
In theoretical work, speculation is never truly harmful. Even if it leads away from the solution (and for each problem, it does lead away in some sense every time but one), it may illuminate other issues.
But again, you do not understand theorists. We want to know what the answers are. In the lack of the ability to actually find the answer, we guess. And when we guess, we are curious who guesses the same way, and who guesses opposite, and why. That is simply human nature. And it doesn't matter whether you find any point to it or not.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: P vs NP debate
« Reply #9 on: Oct 20th, 2006, 7:06am » |
Quote Modify
|
on Oct 19th, 2006, 3:39pm, Icarus wrote:| In theoretical work, speculation is never truly harmful. Even if it leads away from the solution (and for each problem, it does lead away in some sense every time but one), it may illuminate other issues. |
|
And, in another sense, every promising lead exhausted makes progress towards the real solution.
And, of course, for theoreticians, for the most part, it's the journey not the destination that matters - as long as you discover something interesting, it's not important that it's not what you were originally looking for.
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: P vs NP debate
« Reply #10 on: Oct 20th, 2006, 9:41am » |
Quote Modify
|
I suspect that amichail's point is that we are simply too far from making any objective statements about this problem to be debating the matter. Fermat's Last Theorem is a case in point...
When Gauss was asked why he did not pour his genius into solving it, he said,"I confess that Fermat's Last Theorem, as an isolated proposition, has very little interest for me, because I could easily lay down a multitude of such propositions, which one could neither prove nor dispose of."
Gauss, and other great mathematicians so close in history to the birth of the FLT problem, would have surveyed the mathematics available in their day and concluded that "now is not the time".
I have to admit that I am entirely ignorant to the current state of cutting edge mathematics and how far these tools are able to penetrate the P versus NP problem, but from what I've read I suspect that we are as far away from solving it as Gauss was from solving FLT.
To act as self-appointed arbiter, amichail is not saying that research into the problem is pointless, rather debating the matter, as if majority opinion will somehow add strength to the truth or falsity of the claim, should have no place in mathematics.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: P vs NP debate
« Reply #11 on: Oct 20th, 2006, 10:15am » |
Quote Modify
|
On the other hand, the P vs NP problem does have relevence to, for example, cryptography.
If it is likely that P=NP, then all our current cryptography is inherently unsafe. If P=/=NP, then it's (for the moment) safe (ish).
So it has practical value to have some idea of how likely it is that P=/=NP. If it was a 50-50 perceived probability, you really couldn't trust internet banking, or anything like that.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: P vs NP debate
« Reply #12 on: Oct 20th, 2006, 11:36am » |
Quote Modify
|
That's a really good point, towr. However, I do have a query, and this is perhaps showing my ignorance in this matter, but here is my understanding of the difference between P and NP type problems...
P type problems are ones for which an algorithm exists that can solve a general case in a deterministic (polynomial) number of steps.
An NP type problem is one which takes a non-deterministic (polynomial) number of steps.
Any problem that, via transformation, can be shown to be equivalent to another NP problem is called NP hard; NP complete problems are those known to be found in the class of NP problems.
The P versus NP problem asks whether or not P and NP are actually the same set and although we have a class of problems for which we currently have no polynomial time deterministic algorithm, it might be that we just haven't found one yet.
Just because we have a P type problem, does it necessarily mean that it can be solved in a practical amount of time? For example, sorting a list of names into alphabetical order is a P type problem, yet asking for the 1050th alphabetical entry in an unsorted list containing 10100 entries would be "impossible".
So even if we show that P=NP, does it really matter?
Has anyone noticed the irony here? We're debating the point of debating something that we are actually debating! 
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: P vs NP debate
« Reply #13 on: Oct 20th, 2006, 3:21pm » |
Quote Modify
|
Theorists generally do not believe that their opinions add any weight to the truth or falseness of a proposition (at least, mathematicians don't - likely, the softer the science, the more that theorists trust their own opinion). This does not stop them from forming those opinions and sharing them. We just recognize that we could easily be wrong.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
amichail
Senior Riddler
Posts: 450
|
|
Re: P vs NP debate
« Reply #14 on: Oct 20th, 2006, 3:27pm » |
Quote Modify
|
on Oct 20th, 2006, 3:21pm, Icarus wrote:| Theorists generally do not believe that their opinions add any weight to the truth or falseness of a proposition (at least, mathematicians don't - likely, the softer the science, the more that theorists trust their own opinion). This does not stop them from forming those opinions and sharing them. We just recognize that we could easily be wrong. |
|
Yes, but the question is why.
I can think of several possibilities:
* for fun
* to encourage people to pursue a particular direction
* to encourage collaboration
* to encourage funding for various approaches
* to generate interest in the field and attract more students
* to make a hard field sound soft so as not to scare everyone away
* to brag about having predicted an approach would work if someone succeeds with that approach
|
| « Last Edit: Oct 20th, 2006, 3:36pm by amichail » |
IP Logged |
DropZap - a new kind of block elimination game
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: P vs NP debate
« Reply #15 on: Oct 20th, 2006, 5:27pm » |
Quote Modify
|
on Oct 20th, 2006, 3:27pm, amichail wrote:
Yes, but the question is why.
|
|
To earn million dollars!! 
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: P vs NP debate
« Reply #16 on: Oct 20th, 2006, 7:22pm » |
Quote Modify
|
All of those apply to some extent, but I think the main reason is simply the desire to know, and to be seen to know, even when we don't know.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: P vs NP debate
« Reply #17 on: Oct 21st, 2006, 1:26pm » |
Quote Modify
|
on Oct 20th, 2006, 11:36am, Sir Col wrote:| Just because we have a P type problem, does it necessarily mean that it can be solved in a practical amount of time? |
|
Not necesarily, no. But it'll still be easier than an NP problem if NP=/=P (once the input gets beyond a certain size)
Quote:| For example, sorting a list of names into alphabetical order is a P type problem, yet asking for the 1050th alphabetical entry in an unsorted list containing 10100 entries would be "impossible". |
|
Just storing it would be impossible, there aren't enough particles in the galaxy.
If you use a database the size of compiled human knowledge, you could crack it soon enough though. probably faster than factoring a number that's the multiplication of two 128 bit primes.
Quote:| So even if we show that P=NP, does it really matter? |
|
Probably. But yes, it does depend on what deterministic polynomial function turns out to be the bound.
Of course if quantum computing were ever to break through, then we'll suddenly have non-deterministic solvers. And they would break the NP problems with relative ease.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Whiskey Tango Foxtrot
Uberpuzzler
Sorry Goose, it's time to buzz a tower.
Gender:
Posts: 1672
|
|
Re: P vs NP debate
« Reply #18 on: Oct 21st, 2006, 2:38pm » |
Quote Modify
|
On a related note, have you heard the news?
http://www.azonano.com/news.asp?newsID=3209
Still in the planning stages, but I'm optimistic. Crazy times we live in...
|
|
IP Logged |
"I do not feel obliged to believe that the same God who has endowed us with sense, reason, and intellect has intended us to forgo their use." - Galileo Galilei
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: P vs NP debate
« Reply #19 on: Oct 26th, 2006, 12:54am » |
Quote Modify
|
on Oct 20th, 2006, 11:36am, Sir Col wrote:
P type problems are ones for which an algorithm exists that can solve a general case in a deterministic (polynomial) number of steps.
An NP type problem is one which takes a non-deterministic (polynomial) number of steps. |
|
Just to clarify this point: it's not the number of steps that's deterministic or nondeterministic.
A problem is in P if there is an algorithm to solve it on a deterministic Turing machine in polynomial time. "Polynomial time" means that the number of steps needed to run the algorithm is bounded by a polynomial in the size of the problem. A deterministic Turing machine is, basically, an ordinary computer.
A problem is in NP if there is an algorithm to solve it on a nondeterministic Turing machine in polynomial time. So, what the heck is a nondeterministic Turning machine? You can think of it as a computer with an unlimited amount of paralleism. At the start of the computation, the NDTM instantaneously creates one thread for every possible solution to the input problem. In parallel, each thread runs an algorithm (the same algorithm on every thread) to check whether its candidate solution is correct. As soon as some thread detects its candidate is correct, the NDTM stops and outputs that solution. So, a problem is in NP if we can find an algorithm that verifies that a solution to it is correct in polynomial time.
[In explaining an NDTM this way, I've left open the question of whether you have to be able to detect that an answer is incorrect in polynomial time, and if not, whether the NDTM is allowed to run forever if the problem has no correct answers. I must admit I don't remember how these issues are normally dealt with, and I'm too lazy to go look it up right now. Sorry.]
Another way sometimes used to explain an NDTM is that it first instantaneously guesses the correct answer to the problem, then runs an algorithm to verify that the answer really is correct. The guessing is the "nondeterministic" part. I like the unlimited parallelism formulation better because it seems a bit less magical.
Either way, it seems intuitively clear that an NDTM is much more powerful than an ordinary DTM, so one would naively think that an NDTM ought to be able to solve some problems much faster than a DTM. You'd certainly expect that an NP-hard problem could not be solved in polynomial time by a DTM. But as we know, the question is unresolved.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print