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

I for one

[Chuck Chunder]

feel very very stupid after reading that.

Publication Bias

[mSparks43]

Like I said last time. The trouble is, every time someone proves P=NP, the NSA arranges them a little accident.

Re:Yes, they've tried that

[nomoreunusednickname]

I have discovered a truly marvelous proof that P!=NP. But this comment is too deterministic to contain it.

Re:Current Status

[Affenkopf]

The paper was preliminary to begin with. It is currently withdrawn in order to fix minor typos

Minor typos like a ! that m,ade it into the paper by accident.

Re:Hard core

[tehcyder]

"Formal Language Theory" - an undergrad course at my university that dealt with Finite State Automata, Touring Machines, Computability Theory, Complexity Theory,

How cool was that, I assume it was to give you a theoretical basis for the use of car analogies.

Re:Publication Bias

[martin-boundary]

You can't be sure of that. The NSA can only "accident" all those who prove P=NP if the proof verification algorithm requires polynomial time to complete.

Re:I for one

[Anne_Nonymous]

It's not that hard, just try to stay with me...

P != NP
NP has an N in it
So it's not the same as P
P != NP
QEDuh!

If you need any help with any other math stuff, just let me know.

Re:Algorithms

[TheRaven64]

If you think 'polynomial time' and 'quickly' are in any way similar, there's a good chance that you're a theoretical computer scientist.

Re:Mathematicians are gathering to vet this paper

[PachmanP]

Strictly speaking, every computer in the real world is a finite state machine that's complex enough to simulate a universal Turing machine. It's a subtle difference that really only matters if you're considering the math behind it ;)

Oh Snap!!

Re:Mathematicians are gathering to vet this paper

[DiegoBravo]

CS is a subset of biology. Any question in CS can and must be restated in a human brain...