P is not equal to NP

http://arxiv.org/abs/0810.5056

by Anon84 • 18 years ago

30 61 18 years ago

arxiv.org

tlrobinson2• 18 years ago

Ok, the internet says P != NP... does anyone know if this is legit?

llimllib• 18 years ago

arXiv == not peer reviewed. I know I'm not qualified to judge this paper; anybody in here that is?

edit: He appears to be a professor at Uppsala University in sweden: http://user.it.uu.se/~stenake/ .

jacobscott• 18 years ago

Sorry, the key point is that the assertion:

"Therefore, P is not equal to NP, is true and provable in a simply consistent extension B" of B"

does not necessarily imply P \neq NP (the caveat being the B" and B stuff). I'm not really a complexity theory guy, but I would say WHP that this either

(a) does not apply to the most general forms of computation (e.g., what people mean when they ask P =? NP)

(b) is wrong

neilc• 18 years ago

His homepage is amusingly antiquated, even for an academic.

Alex3917• 18 years ago

"arXiv == not peer reviewed."

Although amusingly, I heard that Cornell was sued for not allowing creationists to post their physics theories there.

kevintwohy• 18 years ago

the proof tries to show that p!=np as an extension B" of some Turing machine B -- just read through it and it's all over the place. wouldn't get your hopes up.

s3graham• 18 years ago

http://pdos.csail.mit.edu/scigen/

globalrev5• 18 years ago

He is a professor at Uppsala university in Sweden. The swedish wikipedia article was started in 2006.

globalrev5• 18 years ago

Though after reading the paper it seems like gibberish.

Weird prank though since it seems fairly elaborate.

markessien12• 18 years ago

CS students love dropping four letters: P, NP, O and N. Whenever I want to judge who was a bit too focused on the surface details of computer science, and too little on the real problems, I wait to see if those 4 letters come up in a sentence.

globalrev5• 18 years ago

P vs NP is a pretty real problem, complexity theory is superimportant.

People how can't do proper Big-O-analysis are forever doomed to suck at programming.

markessien12• 18 years ago

That's like saying that people who suck at changing tires of cars can never design or build a car.

Prrometheus2• 18 years ago

If you're performing an analysis on a large data set (say, an index of all the pages on the web), then you'd better know your complexity theory forward, backward, and sideways.

markessien12• 18 years ago

Most CS students I've met hardly understand complexity theory. They just know what algorithms map to what alphabets. And 90% of those that do know complexity theory will never use it in their life. And when they do need it, they need it once or twice in most types of projects. It's a very specialised topic, but just like the singleton pattern, it's easy to understand and sounds impressive, so people tend to namedrop with it.

That's not real CS. CS is mostly about managing complexity across disparate intercommunicating systems, not about the speed of algorithms.

amix• 18 years ago

All things don't have to be practical. There's a lot of insight in knowing the theory, because it's the theory that everything is built upon. Knowing something about complexity theory gives one insight into how problems relate to each other and how complex they are - vital if you are solving problems.

And even if you don't use the theory, it still gives a better understanding fundament. For example, if you understand computability theory, you'll understand why your Java compiler can never determine if your program can halt or not (or any other interesting property of the program), and why you have to use static analysis to give an approximative answer.

And "theory" can be used in practice, an example is Google page rank algorithm which would have been hard to brute force without a good understanding of linear algebra.

markessien12• 18 years ago

Let's say you wanted to write a CD burner program using the lowest level APIs provided by your OS. Which CS theories would you say would be applicable to such a task?

Dilpil• 18 years ago

Whenever I want to see if a prospective employer is a complete hack I drop some of those letters and see if they think their irrelevant.

jhancock• 18 years ago

P = NP, when N is 1. In other cases, I cannot say, but encryption and e-commerce wouldn't exist if it weren't for this conundrum ;)

randomwalker2• 18 years ago

I run the theory of computing blog aggregator (http://feedworld.net/toc/). P =? NP "solutions" show up on there every couple of weeks. The community basically just ignores them because of the virtual certainty that it is flawed. Here is a meta-page discussing the attempts: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

aristus• 18 years ago

Idle question: if you had found something interesting on the problem, what process would you follow to try to get it verified?

randomwalker2• 18 years ago

I'd doubt my sanity :) But if I was convinced I had something interesting, I'd send it to my friends before making it public. If I didn't have friends who were respected theorists, I'd post it to a cs-theory mailing list. Most importantly, I wouldn't title it "P != NP"; I'd rather say, "here's a line of thought that might have implications for P =? NP; please tell me where I'm going wrong."

cousin_it• 18 years ago

Math graduate who knows some complexity theory here. I don't understand the paper and can't even say it's legit. Explanations, anyone?

bayareaguy• 18 years ago

What does it mean for something to be true and provable in a simply consistent extension B" of B ?

wallflower• 18 years ago

In the future (Futurama), P could equal NP :)

http://lance-systems.com/wiki/_media/futurama/2x07-3.jpg?w=2...

http://lance-systems.com/wiki/futurama-mathematics

vecter2• 18 years ago

Chances are, this proof is flawed, like the other hundreds published every year.

P is not equal to NP

Related Stories