8 ms·
P is not equal to NP
- tlrobinson 18y agoOk, the internet says P != NP... does anyone know if this is legit?
- llimllib 18y agoarXiv == 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/ http://user.it.uu.se/~stenake/ .
- jacobscott 18y agoSorry, 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
- deleted 18y ago[deleted]
- neilc 18y agoHis homepage is amusingly antiquated, even for an academic.
- tlrobinson 18y agoI think "minimal" is the preferred term.
- jncraton 18y agoPerhaps, but antiquated probably applies given that he has yahoo listed in his "hot links"
- Alex3917 18y ago"arXiv == not peer reviewed." Although amusingly, I heard that Cornell was sued for not allowing creationists to post their physics theories there.
- kevintwohy 18y agothe 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 18y agohttp://pdos.csail.mit.edu/scigen/ http://pdos.csail.mit.edu/scigen/
- markessien 18y agoCS 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.
- globalrev 18y agoP 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.
- markessien 18y agoThat's like saying that people who suck at changing tires of cars can never design or build a car.
- globalrev 18y agoIf you don't undertand complexity and algorithms you will likely run in t huge performance problems at some point and that will make your whole program useless. No matter the type of programming complexity and algorithms is involved. So it is more like saying "not understanding how a car works will make it very hard for you to design or build one".
- markessien 18y agoYou're completely wrong there. Most programmers will never have to deal with performance as an issue, because most programmers don't work on web based systems, or centralised systems where huge loads impact a single server And for such programmers that do, the real key to performance lies in getting multiple computers to work together, and not in fine tuning algorithms. Most people can intuitively understand the factor by which a linear search is different from a binary search, without any particularly in depth study of complexity theory. This P vs NP thing is just a way for CS students to show off with letters that make their craft seem mysterious. In the real world, one can come through without understanding this. Not understand how a car works? That's really silly. Understanding the speed of algorithms is important, but it's a tiny tiny part of writing large complex programs. Most parts of a programs are not about number crunching, but about information management. (Obviously, I've got an computer engineering degree, and I learned all this, I'm just pointing out that in general and in the real world it has very rarely been neccessary to know this)
- jhancock 18y agoP = 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 ;)
- randomwalker 18y agoI run the theory of computing blog aggregator (http://feedworld.net/toc/ 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 http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
- aristus 18y agoIdle question: if you had found something interesting on the problem, what process would you follow to try to get it verified?
- randomwalker 18y agoI'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 18y agoMath graduate who knows some complexity theory here. I don't understand the paper and can't even say it's legit. Explanations, anyone?
- bayareaguy 18y agoWhat does it mean for something to be true and provable in a simply consistent extension B" of B ?
- wallflower 18y agoIn the future (Futurama), P could equal NP :) http://lance-systems.com/wiki/_media/futurama/2x07-3.jpg?w=288&h=216&cache=cache http://lance-systems.com/wiki/_media/futurama/2x07-3.jpg?w=2... http://lance-systems.com/wiki/futurama-mathematics http://lance-systems.com/wiki/futurama-mathematics
- vecter 18y agoChances are, this proof is flawed, like the other hundreds published every year.