7 ms·

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 l

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.

globalrev 18y 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.
- markessien 18y ago
  That's like saying that people who suck at changing tires of cars can never design or build a car.
  - globalrev 18y ago
    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".
    - markessien 18y ago
      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)
      - DarkShikari 18y ago
        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.
        markessien 18y ago
        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.
  - rgjm 18y ago
    No, it's like saying that people who suck at physics can never design or build a car.
Prrometheus 18y 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.
- markessien 18y 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.
  - jlouis 18y ago
    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".
  - andreyf 18y ago
    That's not real CS. Ahem, you mean it's not real software engineering. SE != CS.
  - Retric 18y ago
    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.
amix 18y 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.
- markessien 18y 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?
  - adamo 18y ago
    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?
    - vecter 18y ago
      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/
    - markessien 18y ago
      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.
Dilpil 18y 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.

globalrev 18y 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.

markessien 18y ago
That's like saying that people who suck at changing tires of cars can never design or build a car.
- globalrev 18y ago
  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".
  - markessien 18y ago
    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)
    - DarkShikari 18y ago
      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.
      - markessien 18y ago
        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.
- rgjm 18y ago
  No, it's like saying that people who suck at physics can never design or build a car.

Prrometheus 18y 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.

markessien 18y 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.
- jlouis 18y ago
  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".
- andreyf 18y ago
  That's not real CS. Ahem, you mean it's not real software engineering. SE != CS.
- Retric 18y ago
  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.

amix 18y 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.

markessien 18y 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?
- adamo 18y ago
  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?
  - vecter 18y ago
    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/
  - markessien 18y ago
    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.

Dilpil 18y 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.