Possible Issues With the P != NP Proof 147
An anonymous reader writes "We previously discussed news that Vinay Deolalikar, a Principal Research Scientist at HP Labs, wrote a paper that claimed to prove P is not equal to NP. Dick Lipton, a Professor of Computer Science at Georgia Tech, analyzed the idea of the proof on his blog. In a recent post, he explains that there have been many serious objections raised about the proof. The post summarizes the issues that need to be answered in any subsequent development, and additional concerns are raised in the comment section."
Re:Mathematicians are gathering to vet this paper (Score:1, Insightful)
Indeed.
Irregardless of whether he's correct or not, the fact that he came out and made it public to be vetted is quite ballsy. Further, the discussion it generates *cannot* be a negative thing.
Kudos to Vinay Deolalikar. You've brought about a minor storm that will bring about positive results.
It looks like (Score:2, Insightful)
Vinay Deolalikar was a little unfortunate in that his unreviewed theory got more attention than he believed it would. It seems his paper offers a new approach, but as it was a first draft had a number of holes and was by no means ready for "prime time".
On the other hand, you could say that broadcasting that you have a solution to one of the most famous remaining unsolved problems was a little ill-advised.
Re:Incompleteness (Score:5, Insightful)
Re:It looks like (Score:4, Insightful)
I read that he intended his proof only to be distributed to a select group of people to help him review it. Then it got away, bits being infinitely copiable.
If someone else released his proof into the wild, we can hardly blame him.
--PM
Re:Mathematicians are gathering to vet this paper (Score:5, Insightful)
>No, it's not. The relationship between computer science and mathematics is similar to the relationship between physics and mathematics:
No it's not the one IS the other and it's the perceived DIFFERENCE that doesn't exist. It's purely a perception -and a DELIBERATE illusion at that, designed to simplify the process. Ultimately it's easilly provable that every computer program is a simple mathematical function - so simple in fact that it is in fact a single number.
There is nothing weird about this- if you know lambda calculus, godel-number and Turing machines it's simple logic. We have never done anything to "split" the fields. All computer science did was to create a (very shallow) layer of pretense through which ot access the maths.
To suggest it is anything OTHER than mathematics is to prove you have absolutely no idea how computers actually work. In the real world- every computer is a universal turing machine.
If you have any real doubt - just consider this: any program COULD be written in lisp.
Lisp is DIRECTLY based on lambda-calculus - in fact the ONLY (minor) difference as small syntactical changes designed to make it easier to TYPE lambda on a computer (it was after-all designed for writing in).
Lamba-calculus is a simple form of mathematical language - like algebra or godel numbers or any of a dozen other ways to write down 2+2=4 that are all just different ways of expressing it designed to be useful for different purposes.
It's true that currently the most popular languages do not follow the lisp "look like the function you are" structure -but this is because in single-CPU machines top-down programs were slightly more similar to how the hardware actually PROCESSED the functions - and that made it easier to program in.
Expect this to change in the next few years - multi-CPU machines are actually EASIER to program for in a functional language like lisp - which makes all those nasty multithreading issues just go away by putting you on the actual mathematics that happens.
Re:Proof that a proof can't exist? (Score:4, Insightful)
Not really. It's proof of a negative which is vastly more difficult than a positive. For example, proving no dogs can have black spots is much harder than dogs can have black spots. You'd have to prove how it's impossible for any dog in existence to get black spots. The opposite only requires existence of 1 dog with black spots.
It's the same with Fermat's Last Theorem: Prove no solutions exist for x^n+y^n=z^n for all integers x,y,z where n is an integer greater than 2. That proof takes hundreds of pages.
Re:I for one (Score:3, Insightful)
NP has an N in it
So it's not the same as P
Prove it.
Re:Mathematicians are gathering to vet this paper (Score:3, Insightful)
Ultimately it's easilly provable that every computer program is a simple mathematical function - so simple in fact that it is in fact a single number.
Every biological system is a physical system, but if you study physics, you'll know next to nothing about biology.
All computer science did was to create a (very shallow) layer of pretense through which ot access the maths.
There is no "pretense". Theoretical computer science is a highly mathematical discipline, but it deals with issues that are of no interest to most other mathematicians. They aren't part of the standard math curriculum either. However, the kinds of mathematics it deals with are of interest to people who build and program computers. That's why theoretical computer science became part of computer science and the computer science curriculum.
Lisp is DIRECTLY based on lambda-calculus - in fact the ONLY (minor) difference as small syntactical changes designed to make it easier to TYPE
Lisp has side effects, lexical scoping, a rich set of data types, and dynamic typing. It is nothing like lambda calculus.
Expect this to change in the next few years - multi-CPU machines are actually EASIER to program for in a functional language like lisp - which makes all those nasty multithreading issues just go away by putting you on the actual mathematics that happens.
Lisp is not a functional programming language, it's a multi-paradigm language that allows you to program in a functional style. Lisp programs are no more parallelizable than C or Perl programs, even when they are written in a functional style.
In order to be a functional programming language, a language needs to prohibit (or at least isolate) side effects. Haskell is about the closest to a pure functional programming language in common use that there is.
I think the fact that you think that Lisp has the benefits of lambda calculus illustrates again why mathematicians shouldn't be doing computer science...