Some loose-talk on the P and NP categories of problems

Do you know what the algorithmic complexity classes of P and NP mean? If not, then look up on the Internet (say, at Wikipedia). Better still, pick up Dennis Shasha’s book of the title: “Out of Their Minds” (It was a great holiday read about a decade back, and it remains so, even today.)

Given below is a very brief (and a very poorly written) outline of what the terms P and NP mean like.

Computer algorithms (and, by implication, the problems they solve) can be broadly classified into two categories: P, short for polynomial-time, and NP, short for non-deterministic polynomial-time. (Mathematicians do not know for sure anything about the classification relations between the two classes—whether they are mutually exclusive or not, whether they are co-extensive (or identical) or not, etc. … ) One way to approach understanding this classification scheme is the following.

When it comes to estimating computational costs of problems, two things help us characterize the situation: (i) the basic (or the “inherent” or the “intrinsic”) size of the computational problem itself, and (ii) the time required for solving that problem using a given algorithm. These two things are separate. Let us look at each one of them in some detail below.

Just to take an example, suppose your problem involves FEM (finite element method) as in computational solid mechanics, or FVM/FDM (finite volume or finite difference methods) as in CFD (computational fluid dynamics). FEM, FDM, FVM, etc. all ultimately translate into a matrix equation of the form [A]{x} = {b}. (Not so, directly, always, but certainly so for the static analysis case anyway.) Which means, they translate into a problem of simultaneous equations, really speaking. If there are N equations with N unknown variables, then the order of the square matrix [A] would also be N. If the mesh you use for your CFD modeling is made finer, the order of the [A] matrix, N, increases. Thus, one can say that N characterizes the basic size of the problem.

There is another consideration: Suppose we are given the particular values of the matrices [A] and {b}, and then are asked to solve the matrix equation [A] {x} = {b}. In short, we have to find what values the elements of the unknown column matrix {x} must possess so that the aforementioned matrix equation would be satisfied.

In finding the solution, we may use, for example, Gaussian elimination, or some other technique. All these techniques require certain multiplications and divisions to be carried out among the elements of [A] and {b}. Now, it is a well-known fact that the computer takes a much longer time (it consumes more number of chip-cycles) to do floating point multiplications and divisions, as compared to doing additions or subtractions. Additions and subtractions are extremely fast (even if done with double precision); multiplications and divisions (and powers and exponentials) are not. Hence, one important way to predict how long a particular solution algorithm would take (say, to solve the equation [A]{x} = {b}) is to ask: How many steps involving multiplication/division are carried out in executing that algorithm. You see, not all algorithms require equal number of multiplications/divisions. Thus, they differ in terms of how many simple steps each has.

It is useful to express the number of (multiplication/division) steps taken in terms of a measure called “Computational Complexity”, denoted as O(N). The capital letter “O” stands for the word “Order” (of complexity). In finding out the values of O(N) for different algorithms, we are not interested in the details of the exact number of steps; only in a rough estimate of the number of steps.

Now, the actual number of steps necessary to solve the problem scales as per the intrinsic size of the problem. Hence, it is useful to normalize the expression for the number of steps, with the size of the problem (N).

Thus, in general, we have an expression of the following form:

O(N) = f(N)

where f(N) is some function of N.

For instance, it is well known that the Gaussian elimination algorithm is numerically fairly stable (even if it is not as stable as so many people routinely suppose), and that its complexity scales as N^3. (The expression for its complexity also include certain lower-order terms like those involving N^2, but these not being dominant are ignored in getting to the *order* of the complexity.)

The aforementioned two factors (N and O(N)) together determine how long a given computational problem would take.

Now, it is easy to tell what the terms P and NP refer to. Well, kind of.

The whole idea is to examine the nature of the expression for f(N). Is it linear in N? That is, does it carry the form: f(N) = k N, where k is some algebraic constant which is independent of N? Even if not, is it at least a polynomial in N? Or is it a really bad expression involving something like e^N or N^N, etc?

If it is the former, then we call it an algorithm of polynomial complexity, shortly denoted as “P”.

On the other hand, if it involves some other relation like the exponential or the factorial relation, then, such a function increases far too rapidly with the increases in N, and so, the complexity (or the time to complete the computational task) becomes impracticably large.

[Here, it would be useful trying out a concrete example. Plot the graphs of N vs f(N) where f(N) is given by: (a) N, (b) e^N, (c) log N, (d) N log N, (e) N^2, (f) 2^N, and (g) N!, for N ranging from, say, 1 to 50. You will immediately appreciate the point that the range of numerical values for complexity can be very wide.]

Often times, it so happens that even if the algorithm to solve a particular class of problems is known, its corresponding f(N) expression is so bad that it is easy to see that the computer will never complete solving the problem using that particular algorithm. The predicted time for the algorithm to complete execution even on the fastest supercomputer can easily exceed billions of years of computer time.

So, in such cases, it’s a bit contradictory. We know the solution—but we don’t. To be more precise: We do know the algorithm, and yet, we also know that the only algorithm that is available cannot complete its run before the Sun collapses (which would happen after billions of years). (Interestingly, the algorithm can be proved to be correct—and yet, it cannot practically complete the run on a real computer.)

A few more points (though I know this blog-entry has by now already gotten into the “novel” mode.)

Sometimes, there are certain helpful mathematical relations embedded within the elements of these matrices—helpful, as judged from the viewpoint of getting solutions faster. These are the relations that appear out of the particular *numerical values* that the matrix elements happen to have—not just their relative *placements* in the matrices. For instance, if the matrix [A] is in the tridiagonal form, then it is possible to solve the equation [A]{x} = {b} in a time of the order of just N, not N^3. This algorithm is called TDMA (which is short for Tri-Diagonal Matrix Algorithm). (OK, it won’t be quite N; there would also be a constant factor appearing in front of N, but the point here is that the constant factor would be, presumably, relatively small, and hence, practically, not very relevant in estimating the order of the computational complexity.) So, if the matrix model is amenable to the TDM algorithm, it can execute very very very fast. (The computational time can come down from years to a few hours. Literally.)

Given this observation, naturally, people have spent some time in finding out if matrices can be “pre-condition”ed so that they can be put in a form that makes them amenable to a faster solution. (There is also another reason for preconditioning: they also try to precondition the numbers if doing so can ensure stability in the subsequent solution procedure.) The idea here is that the preconditioning operation itself would be computationally much lower-cost but that it would put the matrix in such a shape that a much faster running solution algorithm can then be applied to the preconditioned matrix as the second step. Thus, though preconditioning is an *additional* operation, overall, it can still save time.

Another important observation: Practically, it is often possible (or preferable) to settle for an approximate but fast method of solution, if the approximate answer is “close enough.” There is an important category of algorithms that do just this: They supply a series of solution each step of which gives an approximate solution; each step in the series is increasingly better refined. For instance, the multigrid and multipole algorithms exhibit precisely this nature. What determines if an approximate solution is “close enough”? Answer: The purpose behind carrying out the computation.

—–

Most of the above discussion was from the viewpoint of the computational engineer and  not of the computer scientist. Let me add a little bit from the second perspective before closing this piece.

The P and NP classes, as we saw above, are decided in reference to the question: Can you give a polynomial expression for the given algorithm or not. If you can, then the algorithm is in the P class; if not, then, roughly speaking, it would belong to the NP class. This is not at all exact, but it will do for our purposes here. The origin of the NP class rather lies in the automata and languages theory, not in numerical analysis. The two classes are not theoretically well-related to each other except from the viewpoint of the computational complexity angle alone. … Indeeed, whether they are related or not is a million dollar question, literally… The trouble is, no published proof tells whether or why a P-class algorithm can or cannot be formulated for that class of problems which is known as the NP class. For more information on the million dollar prize declared for this open problem, visit The Clay Mathematics Institute, http://www.claymath.org.)

Actually, the absence of a polynomial expression (so far) is just one of the interesting characteristics of NP. The other is: ease of solution verification. What the latter means is the following.

Let us take the traveling salesman problem as a prime example of the NP class of problems. The problem may be stated thus: Suppose a salesman has to visit each of, say, ten cities; suppose those cities are, say, Mumbai, Delhi, Calcutta, Chennai, Bangalore, Ahmedabad, Hyderabad, Pune, and Kanpur. He may visit the given cities in any order, for example, Mumbai first, then Chennai, then Ahmedabad, then Delhi … etc. Or, he may very well choose some other oder for scheduling his visits, say, Delhi first, then Bangalore, then Mumbai… etc. And, of course, there is fare to be paid for the travel in between any given pair of cities. The fare will in general differ from pair to pair. The question is: If the salesman has to cover all the cities and if he is to visit each city exactly once, then, what is the best possible order in which he should visit these cities so that his total traveling expenses are provably lowest possible. (You may also pose this problem in terms of the total distance traveled. The objective would be to minimize the total km for a tour that covers all the cities, visiting each city only once.)

In this example, N, the size of the problem, is 10.

An “easy” (or absolutely sure-shot) way to find the solution would be to make a table consisting of two columns. In the first column, we could make a list of each possible route (that goes through all the cities but visits each city only once). In the second column, we could enter the total fare/distance which would correspond to this particular choice of the route. Once such a table, enumerating all possible routes, is constructed, it would be an easy matter to pick up the route that has the least cost associated with it.

OK. So, what’s the point if the solution is so simple?

The point is this. Before you can decide which particular route would be the cheapest one, you first have to enumerate all the possible routes. And it is this  step—enumeration of the alternatives and finding out the cost for each possible option—which can easily become a computationally expensive operation.

For just 10 cities (N = 10), it is relatively easy to enumerate all possible routes, but that’s only because 10! is such a small number (comparatively speaking). But the factorial function grows very rapidly with N. (If you are a student of science or engineering, right away look up the Stirling approximation for N!) For instance, 5! is just 120, but 10! already is 3,628,800, and 20! is a mind-boggling 2,432,902,008,176,640,000 (i.e. approx. 2.4 billion billions). … When N approaches a value of thousands or tens of thousands (and in practice, we do run into far larger models), then enumeration of each possible alternative itself begins to go out of the reach of even the most powerful super-computer in the world (or all of them put together).

“OK, but why bother?” you may say. “Is it really practical? Does it really matter whether a salesman’s budget goes a little beyond what is absolutely optimal? After all, in the real world, salesmen do travel, and they do sell, and companies do make profits… Why do nit-picking about optimality?”

The answer to that question is: For an actually traveling salesman, minimizing of tour budget may not at all be an issue. Yet, this category of problems is important… If you build a mathematical model of certain practically important problems like choosing the best possible sequence of the forwarding stations for routing of a telephone call (or of Internet data traffic) then that mathematical model looks exactly like the traveling salesman problem. And, billions of dollars (literally) stand to be saved if you can find a method that will tell the optimum route in a fast manner (fast, as in real-time).

OK. So, the traveling salesman problem is practically important.

And, it falls into the NP category.

One funny thing with these NP problems is that if you already have a solution, it is very easy to verify that it indeed is a solution as compared to any other practically posed alternative. Verification (i.e. the one done by sampling) is very easy. But arriving at the solution itself is not. The latter takes too long, or is too pricey. After all, all that you have to do in verification is to pick up some other route arbitrarily, say at random, and verify that between the two given alternatives, the route which corresponds to the actual solution indeed has a lower cost associated with it. That is what verification is all about. So, verification is easy—provided the solution to be verified itself is known in the first place.

Another funny thing with these NP problems is the ease with which they can come up in applications. … Sometimes it looks as if the whole practical world is full of just NP type of problems, and that the P category is rather an exception than the norm. … Incidentally, this precisely is one reason why much creativity is needed even in such seemingly mundane tasks as relational database design. Anybody could establish relations among tables, and proceed to normalize them using certain set rules, but deciding how to abstract what kind of table from what real-world objects… Now, that part is difficult… It’s pretty much an art… And it will continue to be so, precisely because NP is so easy to run into… As another example, consider the problem of optimally populating the school time-table—assigning teachers and students to different class-rooms in different time-slots. This seems to be very simple problem, but it (I suppose) can be proved to be in NP. … The practical world, indeed, is full of NP situations.

All this was a background, really speaking, to get to know a bit about the P and NP classes of algorithms.

Next time, I will give a particularly attractive example of a, vaguely speaking, NP kind of situation. I have been planning to do so for quite some time by now. And the next time, the description won’t involve even this much of mathematics, I promise! (Though, it becomes very tough to write precisely. I began wanting to write a verbal but non-mathematical description; found that I could not; so, ended up making this piece a “loose-talk”. If you have some suggestions to make it less loose, esp. concerning the description of the NP class, then sure do drop a line… Top rankers of IIT Bombay (AIR 4 and all) are especially welcome to attempt writing (LOL!))

Advertisements

2 thoughts on “Some loose-talk on the P and NP categories of problems

  1. Hello.

    I found your article highly informative. I can assume you are a man of great intellect. I want to meet you to know more about you and your talents. I am a single mother living near university circle. Please let me know through your blog if such meetings could be possible. I’ll be keeping an eye on your blogs regularly. Thanks dear!

  2. Dear Ajit

    I see you deleted my first comment. Is it because you want my anonymity or due to your lack of interest in the proposal. Please let me know. And keep up the good work.

Comments are closed.