Maximum PC

Has anyone seen the proof? Does it look valid?

As I understand it, Deolalikar found an example of an NP problem (the Boolean satisfiability problem) that is not 'easily' solvable and therefore, !P.

However, the method that he used (very advanced stats and complexity maths) is beyond me.

Honestly, I was hoping for the opposite result .. if P = NP, the world of maths and CS would suddenly open up (if only in theory).

For the truly insane, here is the paper

Fixed

I approve of this fix.

Actually, I've been reading as much as I can on this proof. I still can't speak to its validity, though. I can say that I'm pretty excited that this problem may have been solved (even if it isn't the result for which I was hoping).

LOL... I haven't had time to sit down and read it yet, but from what I've heard about it, I'd probably be happy if I were able to follow half of the theorems proven in this paper! =)


The latest commentary that I've seen on the status of the paper suggests that the proof probably won't stand (as is), but it does use some new approaches that might provide valuable insight leading to additional work in the future.


Just curious, why do you want it to go P = NP instead?

Why? Because it'll cause a great deal of FUD around cryptography, but also because it means that there are answers to so many interesting questions.

Two very different reasons, I know.

I suppose I should say 'elegant, solvable (in human-time) solutions to so many interesting questions' rather than just answers.

I assume that you're making this statement because of prime factorization, right? This is actually one of the problems that people aren't really too sure about which complexity class to place it. Proving P = NP might not matter all that much in this case. Of course, it mattering would spur on alternative encryption strategies and/or increased awareness of existing algorithms not based on prime factorization.


Well, it might be a bit less useful in the real-world than many of us have come to believe. First, there is the possibility that the solution is something like n^100, which would probably not prove to be very useful. Second, while many NP problems might be interesting to computer scientists and mathematicians, I'm not too sure that it will be viewed as warmly by the general media unless computers could suddenly perform tasks like language translation, speech recognition and object recognition perfectly. I don't believe that these tasks are actually in NP -- ditto for Chess, Go, and many other games. Of course, many of the computationally expensive tasks that people already perform, eg HDTV encoding, are presumably already in P and won't benefit from a stunning P = NP finding.

Anyways, I hope to get to the paper early next week. It should be interesting.

http://rjlipton.wordpress.com/2010/08/1 ... ars-proof/

Not a proof. Granted, I understand very little in the critique, but I'm quite sure a true proof would be recognized very very widely.

Yeah... by all accounts, it appears that the proof isn't going to hold up.

Did anyone else happen to see this though?

Beating A Forty Year Old Result: Hamilton Cycles

The idea that all NP problems may eventually be shown to have an exponential time worse-case is pretty darn interesting.

The speed up from 2^n to 1.657^n is actually quite a bit more significant than I would have thought initially...

Why not just do 1000 problems of each and whichever holds out the most wins, heh.

Because that isn't a proof.

It was a joke

Prove it.

It was my problem, so I know how to solve it.

Huh? I don't follow this proof... or joke.

Proof it.

Here is an IBM research video discussing the history and failings of the proof.

I'm only about half-way through the video at the moment, but it seems to be worth a watch.

Now there is some serious science reporting!

So the idea of this is to figure out ant prove that as a problem gets larger, it takes longer time to solve right? But then once you have your guess it can take a short time of checking if it's true.

I suppose that this is true if you're running your calculations from a single computer, on a single core/thread...

I come to think of the salesman problem, or a similar problem.



There is a case here that I can think of in which may not be P=NP but can come close, I do believe. But let me sleep on it haha.

Ok, I reviewed the paper & came to this conclusion.
P = NP
They are opposites

Problem = No Problem

Have a good day.