Slashdot Mirror
Possible Issues With the P != NP Proof
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."
Fails at step 3.
Quidnam Latine loqui modo coepi?
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
>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.
Unicode killed the ASCII-art *
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.
Well, there's spam egg sausage and spam, that's not got much spam in it.