Math is the foundation of Computer Science. By Computer Science I mean the study of algorithms and computation and information theory. Computer Programming is the application of CS principles into making concrete structures. Computer Engineering is the application of CS principles into designing concrete systems. As I define it here Computer Science is nice to know (and rather important for engineers), but it omits many of the real-world practices that professionals use and have developed.

Why is math important to Computer Science? CS tries to quantify and determine and distinguish between different algorithms. An algorithm is a computational recipe, it's a way of doing a certain task, be it picking a "random" number or sorting a list of names or drawing a 3d landscape in realtime. A lot of CS is about calculating how efficient algorithms are in terms of space and time and complexity. Computer Engineering takes those findings and uses the algorithms as tools to solve problems while taking into account project requirements. Computer Programmers do the actual coding.

One of the computationally hard classes of problems are NP problems. Let's go back a bit. P problems are solvable in polynomial time (i.e. there's an algorithm that solves the problem in polynomial time). A polynomial is an equation of the form a(n^x) + b(n^y) + c(n^z) + ... where x > y > z and so on. If we're only looking at an approximation then we need only look at the first term, which will overshadow the other terms given a large enough value of n. (Looking at the equation, I probably got something wrong, but the basic idea is still correct). So an algorithm that is n^6 is still polynomial, even though the time it takes to finish goes up tremendously fast.

Even though P problems can take a very long time (if x is more than 2 or 3) for large values of n, they are still better than NP problems. NP means non- polynomial, and describe a class of problems for which no P-type algorithm has been found. There are several classes of NP problems (NP hard comes to mind, although I don't think there's an NP soft). Solving one NP problem (i.e. finding a P algorithm for an NP problem) would also solver the other NP problems in the same class. This is one of the big research problems in Computer Science.

Why are NP problems important to solve? Unlike Fermat's Theorem which was proven a year or two ago, NP problems have real world applications. Take the classic traveling salesman problem. Given a set of cities that a salesman must visit, and an incomplete set of distances between cities (by incomplete I mean that not every city has a direct path to another city, like in a roadmap). Given that information, compute the least distance path that has the salesman visit every city. An algorithm that can solve this can be applied to airline travel or UPS deliveries, etc.

So far, no one has come up with a computer algorithm that can solve the problem in polynomial time. Without using heuristics (heuristics being rules-of-thumb that can help an algorithm find a good solution quickly, but don't guarantee that the solution is the best solution) the only way to be sure is to compute every path starting from every city and then picking the lowest cost path. So there are n ways to pick the first city, (n-1) ways to pick the second, (n-2) to pick the third etc until you pick the last city. This is a n! (n factorial) algorithm and hopefully it's obvious to see that any polynomial algorithm (of degree x, degree of a polynomial is the highest exponent) will be faster than an n! algorithm once n > x (assuming the same constants, even with different constants we can see that n! goes up faster than n^x so eventually n! will be larger and less efficient).

So why am I bringing this up? Anatoly Plotnikov has come up with an O(n^6) algorithm for solving the Minimum Clique Partition Problem, one of the NP problems. There is no way that I'm going to ever understand the paper, but if he has found an answer then he will be one of the great heroes of Computer Science. That's if he has found a solution, most people having concluded (without being able to verify) that some problems have no P solutions. (Consequently that's the other way to go about it: prove that a class of problems are NP and have no P solutions and that way people would stop wasting their time trying to solve it. That would also make you famous, at least in circles that I have a chance of hearing about).

Well, that's it for my little bit of Computer Science. Like I may have said before: I use very little of what I learned in Computer Science in my everyday work life. But it's that knowledge that separates me from a code monkey. Uk uk.