P is not equal to NP(arxiv.org)
arxiv.org
P is not equal to NP
http://arxiv.org/abs/0810.5056
63 comments
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
Idle question: if you had found something interesting on the problem, what process would you follow to try to get it verified?
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."
Ok, the internet says P != NP... does anyone know if this is legit?
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/ .
edit: He appears to be a professor at Uppsala University in sweden: http://user.it.uu.se/~stenake/ .
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
"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]
"arXiv == not peer reviewed."
Although amusingly, I heard that Cornell was sued for not allowing creationists to post their physics theories there.
Although amusingly, I heard that Cornell was sued for not allowing creationists to post their physics theories there.
His homepage is amusingly antiquated, even for an academic.
I think "minimal" is the preferred term.
Perhaps, but antiquated probably applies given that he has yahoo listed in his "hot links"
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.
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 ;)
Math graduate who knows some complexity theory here. I don't understand the paper and can't even say it's legit. Explanations, anyone?
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
http://lance-systems.com/wiki/_media/futurama/2x07-3.jpg?w=2...
http://lance-systems.com/wiki/futurama-mathematics
What does it mean for something to be true and provable in a simply consistent extension B" of B ?
Chances are, this proof is flawed, like the other hundreds published every year.
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.
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.
People how can't do proper Big-O-analysis are forever doomed to suck at programming.
That's like saying that people who suck at changing tires of cars can never design or build a car.
If 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".
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".
You'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)
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)
What you really mean is "in my job, I haven't had to use these particular concepts," which is of course completely anecdotal, and, given the response (and voting) of other HN users, probably not a very common situation.
In my business, the difference between polynomial and NP is the difference between a thousand clocks and a million clocks, the difference between a practical quantization optimization algorithm and a totally useless one. And if you don't understand that before trying to write it, you're going to waste days of coding time on a pipedream.
NP problems are incredibly common in almost all fields one could imagine. Not being able to identify them before wasting time trying to optimally solve them is a recipe for disaster and the sign of a completely incompetent programmer.
In my business, the difference between polynomial and NP is the difference between a thousand clocks and a million clocks, the difference between a practical quantization optimization algorithm and a totally useless one. And if you don't understand that before trying to write it, you're going to waste days of coding time on a pipedream.
NP problems are incredibly common in almost all fields one could imagine. Not being able to identify them before wasting time trying to optimally solve them is a recipe for disaster and the sign of a completely incompetent programmer.
The voting of HN users will never be relevant to my opinions.
I have needed to use the concepts in my job, and I'm pointing out that these are really not what computer science is about. Anybody who focuses on algorithmic efficiency based off speed is looking at the bark of a tree and failing to recongize that the forest is being cut down.
Our problems with CS have become wider and bigger and different. We are having to deal with abstractions of very complex behaviour, and N vs NP, even though it should be understood, is not something that needs to be focused on in-depth in most programming activities today.
NP problems are not 'incredibly common' in most programming activities. They are common in most programming fields, just as molecules are common in most human beings, but it does not mean that all human beings have to bio scientists.
The reason I am arguing against this N-NP name dropping is that I believe that to properly evolve in computer science, we need to abstract away the details and focus on the bigger picture. For that to happen, we WILL need a generation of programmers that should not need to know this stuff. Just like many new programmers do not know assembler.
You're obviously preaching to the choir here, so lots of people will agree with you. But I am convinced that the only path forward we have is by wrapping complexity in aggregates, so that programmers can create even more complex machines. We need to get rid of the details for a certain class of high level programmers, otherwise we will not be able to break out of the existing models we have.
I have needed to use the concepts in my job, and I'm pointing out that these are really not what computer science is about. Anybody who focuses on algorithmic efficiency based off speed is looking at the bark of a tree and failing to recongize that the forest is being cut down.
Our problems with CS have become wider and bigger and different. We are having to deal with abstractions of very complex behaviour, and N vs NP, even though it should be understood, is not something that needs to be focused on in-depth in most programming activities today.
NP problems are not 'incredibly common' in most programming activities. They are common in most programming fields, just as molecules are common in most human beings, but it does not mean that all human beings have to bio scientists.
The reason I am arguing against this N-NP name dropping is that I believe that to properly evolve in computer science, we need to abstract away the details and focus on the bigger picture. For that to happen, we WILL need a generation of programmers that should not need to know this stuff. Just like many new programmers do not know assembler.
You're obviously preaching to the choir here, so lots of people will agree with you. But I am convinced that the only path forward we have is by wrapping complexity in aggregates, so that programmers can create even more complex machines. We need to get rid of the details for a certain class of high level programmers, otherwise we will not be able to break out of the existing models we have.
I think we turned what was an innocent and perhaps true remark to a certain degree(people like to namedrop it) into a quarrel here.
I'm not saying that computer science is all day P vs NP philosophy. I'm just saying that you have to know complexity and algorithm theory to work in the field just as you have to understand the hardware, you might get by most of the time without it but when you don't, if you don't even know where to start, you'll have a mountain to climb rather than a little tree.
* However your remark about how this should be abstracted away and people shouldn't have to know it in the same way people don't have to know assembler now, that's not the same thing at all.
I'm not saying that computer science is all day P vs NP philosophy. I'm just saying that you have to know complexity and algorithm theory to work in the field just as you have to understand the hardware, you might get by most of the time without it but when you don't, if you don't even know where to start, you'll have a mountain to climb rather than a little tree.
* However your remark about how this should be abstracted away and people shouldn't have to know it in the same way people don't have to know assembler now, that's not the same thing at all.
Well, what I've learned from this is that people are really sensitive about their P-NP knowledge. Look at the scale of the down-moding I'm getting :)
I think I'd better stop making trying to make my point now, it apparently is not being understood.
I think I'd better stop making trying to make my point now, it apparently is not being understood.
I'm guessing most of the downvotes are due to the confusion between software engineering and computer science.
From wikipedia:
Computer science (or computing science) is the study and the science of the theoretical foundations of information and computation and their implementation and application in computer systems.
Software engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software.
--
I think you are talking about software engineers and everyone else is defending computer scientists.
From wikipedia:
Computer science (or computing science) is the study and the science of the theoretical foundations of information and computation and their implementation and application in computer systems.
Software engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software.
--
I think you are talking about software engineers and everyone else is defending computer scientists.
The excessive downvoting has become something of a recent fad here. I'd have put your comments to -1, but not further, because I do, like apparently many, believe that your notions are fundamentally flawed.
Complexity theory isn't hand-wavey-ultra-complicated-irrelevant CS; it's first / second semester stuff. It's fundamental enough that it's a cognate for most lots of physics, math and engineering students. That's to say, that it's relevant enough that if you're even doing something moderately related to computer science that it's worth knowing.
Are there a lot of jobs where you don't need to know this stuff? Well, I think there are a lot of jobs where you can get by without knowing basic CS, but it'd still benefit you from time to time to be able to apply these sorts of abstractions.
"Why is this function so slow?"
"Its runtime is quadratic."
"Huh?"
In my particular case, not knowing fundamentals of CS theory would cut me out of being able to work on precisely the problems that I find most interesting in programming.
Complexity theory isn't hand-wavey-ultra-complicated-irrelevant CS; it's first / second semester stuff. It's fundamental enough that it's a cognate for most lots of physics, math and engineering students. That's to say, that it's relevant enough that if you're even doing something moderately related to computer science that it's worth knowing.
Are there a lot of jobs where you don't need to know this stuff? Well, I think there are a lot of jobs where you can get by without knowing basic CS, but it'd still benefit you from time to time to be able to apply these sorts of abstractions.
"Why is this function so slow?"
"Its runtime is quadratic."
"Huh?"
In my particular case, not knowing fundamentals of CS theory would cut me out of being able to work on precisely the problems that I find most interesting in programming.
I understand the theory perfectly, having a pretty good degree in CE. My argument has nothing to do with my personal situation, I'm running an argument based on a theoretical situation.
If you look at any other field containing "engineers", the mathematical basics are not abstracted away over time. Mechanical engineers have taken courses in math and physics; that part never goes away. Technicians are the guys who may have impressive technical knowledge and skills but never learned the theory behind it. From the perspective of the old-fashioned engineers, if a programmer calls himself a "Software Engineer" instead of a "Computer Programmer", he'd better have some fundamentals to back it up. (Of course not all programmers need to be engineers -- technicians are great. But somebody in the building needs to known why things work they way they do.)
Actually, you're right. My study is in Computer Engineering with focus on robotics, so my focus has been different so far.
Search engines and scientific computing spend a lot of time searching for more efficient algorithms and more efficient approximations of algorithms when the size of the data sets become ridiculously large. They might not be "real world" enough for you, but I would like to work at a search engine after I graduate.
What is this "bigger picture"? So far you've offered a smaller picture, by telling us what should not be learned. What should be learned instead?
No, it's like saying that people who suck at physics can never design or build a car.
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.
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.
That's not real CS. CS is mostly about managing complexity across disparate intercommunicating systems, not about the speed of algorithms.
N vs NP is not really that important because n^1000 might as well be NP. However, understanding that something is O(1) vs O(log x) vs O(x) vs O(x log x) vs (x ^2) and you can often drop down a level depending on what tools you use can becomes vary important the second you start testing small datasets to represent large ones. Wow 1000 takes 1/2 a second and 2000 takes 2 seconds I wonder how long it's going to take when I dump a million in there?
I have written low level networking code and you can abstract that to high level networking code. You can make handling thousands of threads easy. But, there is nothing to abstract away when you want to know everything within 10 feet of each object in a list. Granted, there are way's of solving that with a billion object list but they all depend on how the data is setup and not a general solution.
I have written low level networking code and you can abstract that to high level networking code. You can make handling thousands of threads easy. But, there is nothing to abstract away when you want to know everything within 10 feet of each object in a list. Granted, there are way's of solving that with a billion object list but they all depend on how the data is setup and not a general solution.
"P vs NP is not really that important because n^1000 might as well be NP"
And yet P seems to capture pretty well the concept of "problems for which there are efficient algorithms." For whatever reason, no algorithm seems to have a complexity like O(n^1000). I don't know why. I'm not sure anyone does. But the highest exponent I can think of right now is n^12 for the original upper bound on the AKS primality testing algorithm, and I think that was later reduced to n^6.
And yet P seems to capture pretty well the concept of "problems for which there are efficient algorithms." For whatever reason, no algorithm seems to have a complexity like O(n^1000). I don't know why. I'm not sure anyone does. But the highest exponent I can think of right now is n^12 for the original upper bound on the AKS primality testing algorithm, and I think that was later reduced to n^6.
Ok n^1000 was a little over the top but how far you can scale is still outside the question of P vs NP.
N^2 means 10 million is not acceptable in a reasonable amount of time. (10^14)
N^6 hit's 10^14 at 216.
N^log N hit's 10^14 a little after 5500 [edit 5517] and it takes 1,000,001 before it's worse than N^6 but it's all downhill from there.
N^2 means 10 million is not acceptable in a reasonable amount of time. (10^14)
N^6 hit's 10^14 at 216.
N^log N hit's 10^14 a little after 5500 [edit 5517] and it takes 1,000,001 before it's worse than N^6 but it's all downhill from there.
What are the units? 10^14 is indeed far too much if it's seconds, but might not be beyond reason for a set of size 10 million if it's nanoseconds (then you have a bit under three hours.) So think about which units this would actually have.
Indeed, an algorithm being in P may not be sufficient to scale, but if a problem is NP-complete (assuming P != NP) there's almost certainly no scalable algorithm for it.
Indeed, an algorithm being in P may not be sufficient to scale, but if a problem is NP-complete (assuming P != NP) there's almost certainly no scalable algorithm for it.
(10^14) nanoseconds = 1.1574 days
I should have said If N^2 means 10 million... Anyway, I tend to think of 10^10 nanoseconds as vary bad (10 seconds) and (10^14) > 1 day as unreasonable, but that's just a rule of thumb from the days of 1Ghz CPUS's.
I should have said If N^2 means 10 million... Anyway, I tend to think of 10^10 nanoseconds as vary bad (10 seconds) and (10^14) > 1 day as unreasonable, but that's just a rule of thumb from the days of 1Ghz CPUS's.
I find complexity theory to be extremely important to CS students. In fact, complexity theory is exactly what differentiates the good programmers from the bad programmers. Not that they use an asymptote in their day-job, but because they have an inherent knowledge of the cost of an algorithm. Now of course, in practice it might be the "bad" algorithm that wins because N is small enough. It often is.
But the masters inherently know when they need to switch to a more complex algorithm with a better bound. You can't get that without understanding of complexity theory.
There are several really interesting problems that people might want an algorithm for which lies in the NP space. Granted, most ${STANDARD} programming is not about the solution to such problems. But then again, it was not the intention that people skilled in theoretical CS should use their time on such problems. In this sense, the theoretical people tend to be far far ahead the "real world".
But the masters inherently know when they need to switch to a more complex algorithm with a better bound. You can't get that without understanding of complexity theory.
There are several really interesting problems that people might want an algorithm for which lies in the NP space. Granted, most ${STANDARD} programming is not about the solution to such problems. But then again, it was not the intention that people skilled in theoretical CS should use their time on such problems. In this sense, the theoretical people tend to be far far ahead the "real world".
That's not real CS.
Ahem, you mean it's not real software engineering. SE != CS.
Ahem, you mean it's not real software engineering. SE != CS.
Computer Science is a big field, and I get the impression you think what you do is the only relevant part. It's not.
[deleted]
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.
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.
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.
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?
What if you add the constraint that the user has a library of a N songs and you wanted to fill the CD completely for a road trip?
An approximate solution would work for the above but you can see how easily it pops up: http://en.wikipedia.org/wiki/Subset_sum_problem
Complexity theory is the coolest thing I've learned. I think thats why people study it - they don't particularly care about the practicality of their work. Which is ok. Breakthroughs and connections are often unexpected (It's hard to discuss cryptography without understanding it), so you might as well let the smart people do whatever they feel like in academia than declare x,y,z to be the 'real' issues people are facing that should be solved - we have the market/industry for that.
Incidentally, I wasted a lot of time thinking about http://en.wikipedia.org/wiki/Partition_problem in high school - I was trying to figure out how to make the A-side and B-side of a mix tape of equal length.
An approximate solution would work for the above but you can see how easily it pops up: http://en.wikipedia.org/wiki/Subset_sum_problem
Complexity theory is the coolest thing I've learned. I think thats why people study it - they don't particularly care about the practicality of their work. Which is ok. Breakthroughs and connections are often unexpected (It's hard to discuss cryptography without understanding it), so you might as well let the smart people do whatever they feel like in academia than declare x,y,z to be the 'real' issues people are facing that should be solved - we have the market/industry for that.
Incidentally, I wasted a lot of time thinking about http://en.wikipedia.org/wiki/Partition_problem in high school - I was trying to figure out how to make the A-side and B-side of a mix tape of equal length.
That has little to do with burning a CD. The particular problem you bring as an example is a small and completely optional problem that one would be faced compared to the entire task. And I could look up a solution in 15 minutes.
And thus, you've just gone and demolished your entire argument. There is no solution in reasonable time, which is why mwerty brought it up.
This whole downvote storm is because your OP was "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." and there is a crowd of people here whose work on real problems involves those four letters all the time & couldn't be done without extensive knowledge about them and discussing them endlessly.
Maybe they don't come up so often when writing cd burning programs or robotics (though I find the latter hard to believe since any planning algorithms should hit up against this quickly), but other people have their own real problems where it does. I'm trying hard not to be dismissive here, even though your original post reeked of dismissiveness.
This whole downvote storm is because your OP was "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." and there is a crowd of people here whose work on real problems involves those four letters all the time & couldn't be done without extensive knowledge about them and discussing them endlessly.
Maybe they don't come up so often when writing cd burning programs or robotics (though I find the latter hard to believe since any planning algorithms should hit up against this quickly), but other people have their own real problems where it does. I'm trying hard not to be dismissive here, even though your original post reeked of dismissiveness.
If only you get to decide what's small, what's completely optional and whats the entire task, you are right and I submit.
You would have to be crazy smart to figure out P,NP, etc. in 15 minutes without pre-existing knowledge of it.
You would have to be crazy smart to figure out P,NP, etc. in 15 minutes without pre-existing knowledge of it.
The low level API calls that you make, make use of the OS scheduling. But you may claim that you can be agnostic to this fact. On the other hand optimizing your code to run efficiently can be done either using your gut feeling, or by understanding the complexity of your code, to make it run faster, with fewer calls, and optimal buffer usage. Would that suffice as an answer to your question?
The low level APIs do not require any knowledge of the OS scheduling. The code is not complex in the way you think it is - there is little algorithmic behaviour in a CD Burning task.
Let's see: predictive I/O scheduling, buffer management, and cryptographic checksums all seem like they fall within the realm of "algorithms," and all would be fairly necessary to a well-behaved non-trivial CD-burning system. And yes, you would need to have some idea how the operating system schedules tasks if you are to have any luck maintaining write throughput to keep from under-buffering.
That would be over-engineering. You want to keep your buffer full:
if buffer not full:
wait (time for 5 writes);
write to 5 * read_size to buffer;
Sure, you could do it more complex, but then you create fragile code at a spot when a simppler solution would work fine.
if buffer not full:
wait (time for 5 writes);
write to 5 * read_size to buffer;
Sure, you could do it more complex, but then you create fragile code at a spot when a simppler solution would work fine.
But even the fact that you have to decide on the buffer size is a matter of understanding the theory. Choosing to multiply by 5 too. Why is it 5 and 12? Why the buffer size is not the half or double the size that it has? How can you prove that you have chosen the correct values if not by theory?
Exactly. Check out the Linux O(1) time scheduler.
http://www.ibm.com/developerworks/linux/library/l-scheduler/
http://www.ibm.com/developerworks/linux/library/l-scheduler/
You don't need a CS degree to read the API documentation. But if you do bother getting a CS degree, shouldn't you learn something beyond how to look up the cdrom API documentation?
Some knowledge about OS design would be good, I suppose. You've got a degree; what fundamental knowledge do you find the most helpful? (Meaning, things that will be relevant in 20 years, rather than familiarity with what's hot right now.)
Some knowledge about OS design would be good, I suppose. You've got a degree; what fundamental knowledge do you find the most helpful? (Meaning, things that will be relevant in 20 years, rather than familiarity with what's hot right now.)
The most fundamental knowledge a university has to offer is to learn how to learn.