wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> P vs NP debate
        
(Message started by: amichail on Oct 18^th, 2006, 4:19am)

Title: P vs NP debate
Post by amichail on Oct 18^th, 2006, 4:19am

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.

Title: Re: P vs NP debate
Post by Icarus on Oct 18^th, 2006, 6:31pm

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.

Title: Re: P vs NP debate
Post by amichail on Oct 19^th, 2006, 12:40am

on 10/18/06 at 18:31:39, 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.

Title: Re: P vs NP debate
Post by towr on Oct 19^th, 2006, 1:02am

on 10/19/06 at 00:40:21, 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.

Title: Re: P vs NP debate
Post by amichail on Oct 19^th, 2006, 1:07am

on 10/19/06 at 01:02:37, towr 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.

Title: Re: P vs NP debate
Post by rmsgrey on Oct 19^th, 2006, 5:19am

on 10/19/06 at 01:07:44, amichail 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. How far from any obvious lines of attack did the eventual proof of Fermat's Last Theorem end up?

Title: Re: P vs NP debate
Post by amichail on Oct 19^th, 2006, 5:23am

on 10/19/06 at 05:19:45, 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?

Title: Re: P vs NP debate
Post by rmsgrey on Oct 19^th, 2006, 5:36am

on 10/19/06 at 05:23:20, 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.

Title: Re: P vs NP debate
Post by Icarus on Oct 19^th, 2006, 3:39pm

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.

Title: Re: P vs NP debate
Post by rmsgrey on Oct 20^th, 2006, 7:06am

on 10/19/06 at 15:39:57, Icarus wrote:

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.

Title: Re: P vs NP debate
Post by Sir Col on Oct 20^th, 2006, 9:41am

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.

Title: Re: P vs NP debate
Post by towr on Oct 20^th, 2006, 10:15am

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.

Title: Re: P vs NP debate
Post by Sir Col on Oct 20^th, 2006, 11:36am

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 10⁵⁰th alphabetical entry in an unsorted list containing 10¹⁰⁰ 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! ;D

Title: Re: P vs NP debate
Post by Icarus on Oct 20^th, 2006, 3:21pm

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.

Title: Re: P vs NP debate
Post by amichail on Oct 20^th, 2006, 3:27pm

on 10/20/06 at 15:21:31, Icarus wrote:

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

Title: Re: P vs NP debate
Post by Sameer on Oct 20^th, 2006, 5:27pm

on 10/20/06 at 15:27:34, amichail wrote:

Yes, but the question is why.

To earn million dollars!! :D

Title: Re: P vs NP debate
Post by Icarus on Oct 20^th, 2006, 7:22pm

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.

Title: Re: P vs NP debate
Post by towr on Oct 21^st, 2006, 1:26pm

on 10/20/06 at 11:36:59, 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 10⁵⁰th alphabetical entry in an unsorted list containing 10¹⁰⁰ 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.

Title: Re: P vs NP debate
Post by Whiskey Tango Foxtrot on Oct 21^st, 2006, 2:38pm

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...

Title: Re: P vs NP debate
Post by TimMann on Oct 26^th, 2006, 12:54am

on 10/20/06 at 11:36:59, 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.