Recently I wrote about computational software and said that EDA algorithms are all "intractable". That was in the post Computational Software. What does intractable mean? If you know anything about algorithms, you might have heard terms like "polynomial time" or "exponential". Or even more technical terms like "NP-hard" or "NP-complete".

When I was an undergraduate studying computer science, one of my lecturers told me that he expected someone to prove that "P≠NP" in the following few years. In fact, it is still open. So open, in fact, that it is one of the seven open problems in mathematics that the Clay Institute in 2000 made one of the millennium prize problems for which you win $1M for solving. Or you can just prove the Riemann Hypothesis. Both these statements, that P does not equal NP, and that the Riemann Hypothesis is true, are are not really open questions. There is simply no way that they are not both true, except perhaps in weird irrelevant corner conditions. But nobody can prove either of them. It will be front-page news on the New York Times when someone proves one of them. And that is not a throwaway remark, these problems are that significant.

We talk about EDA here on this blog, so the Riemann Hypothesis is not really relevant. If you want to sound knowledgeable, you can tell people that "the non-trivial roots of the zeta function have real part equal to ½" but you'll struggle if someone follows up by asking what that means. It's not like Fermat's Last Theorem or the Four Color Problem, that are mathematically deep but easy to explain to a middle schooler. P and NP are relevant to EDA though.

Finding the Tallest Student

P stands for polynomial time. Algorithms in computer science are often classified for efficiency using "big O" notation. O(n) or O(n²). Let me try and explain for non-programmers. If you have to decide who is the tallest student in a class, and there are 25 students, there is no way you can do better than looking at all 25 of them. If you miss one out, that student might turn out to be the tallest. That is O(n). The "n" in O(n) is 25, the size of the problem we are dealing with. You need to look at all students once but no more than once.

If you had to order all the pupils from tallest to shortest, there's no way to do it by looking at each of them once. So how would you do it? The obvious way is to take the first student, then look at the second and see if he or she is taller than the first, and if so, swap them. Then look at the third student and slot them in among the first couple. Keep going until you get to the last student, who you will have to find the right place in the previous 24. This is O(n²) since, in the worst case, the students are in reverse order and you have to look at each student and then look at every student again to discover that he or she is the new first place. There are better algorithms than this, the best being O(n log n). But this algorithm is not stupid, and even has a name "bubble sort". For small problems, it is so simple to implement that it is hard to beat. For sorting a million pupils it is really slow. However, compared to worse algorithms, any polynomial algorithm like this is regarded as fast, and is in P. So it is considered quick.

I'm not going to explain all the terms I already used like NP and NP-complete. But I will explain why the P≠NP is important. Since it is not yet proven, this comes down to the fact that nobody knows whether problems that can be verified quickly can also be solved quickly. In this context, "quickly" means in polynomial time, so O(n^x) for some x. Although, in practice, if x is a huge number, this is irrelevant for a practical domain like EDA. But for most algorithms, x is 2 or 3 like in the sorting the student example I explained above. I explained P above. NP means that the solution can be verified in O(n^x) time but nobody knows a way to produce that solution so quickly.

Lots of problems are easy to verify, but seem to be hard to do. For example, you probably can multiply 71 by 83 (you can even use your phone, just go ahead, it doesn't make any difference). But to tell me the factors of 5,893 is much harder (yeah, use your phone if you can). That is a problem that is easy to verify but hard to do. If you get told the solution is 71 and 83, you can multiply them and confirm that you get 5,893. But the other way around is hard. It is possible that there is some way of factoring 5,893 easily but nobody knows it. In fact, the security of the internet depends on there being no easy way to do it, since RSA encryption, that underlies the key exchange used to put that little padlock on a website in your browser bar, depends on it being hard. Of course, for 5,893 you can just try all the small numbers, but if the number is 200 digits long that doesn't work because it takes weeks of computer time.

Traveling Salesmen

A famous problem in NP that is easy to explain is the "traveling salesman problem". A salesman (paging Willie Loman) has to visit some cities driving in his car, so what is the best route. (Yes, the salesperson could be a woman, but the problem dates from 1930 or maybe 18xx something.) The problem is to find the optimal route. Obviously, if there are a handful of cities, you can try all the routes. But it turns out nobody knows a solution much better than that to find the optimal route, although there are lots of algorithms that get close (like within 1% of optimal).

I had to solve this problem for myself when I was about 20, long before I'd ever heard the words "traveling salesman". I was writing code to program a numerically controlled sheet metal punching machine. For a punch and die, there were lots of places to make the required holes, so what was the best route to make the machine use? The obvious ideas are "nearest neighbor" or "left to right". These are both terrible in practice because of patterns that "fool" them. But they are basically good ideas.

I came up with an algorithm that worked pretty well for the size of designs we were making (there were not a million holes to be punched, obviously). I worked from left to right but used the square of the difference for holes in the backward direction, making a stray hole left far behind really desirable to punch soon before it got left in the far distance. Two lines of holes that were almost on the same line would be punched in order; two lines that were far apart would be done one after the other.

I thought it was a pretty neat solution to an everyday problem I'd run into. It was a year later studying computer science that I discovered it was a known-hard problem with no perfect solution.

Intractable in EDA

So what does intractable mean? If you are a professional complexity theorist, it means that it has no polynomial-time solution. But for an EDA engineer, polynomial time with a big index is the same as useless. In fact, any index bigger than 1. Even an O(n²) algorithm is intractable when you are dealing with hundreds of billions of pieces of interconnect on a chip. Let alone trillions of polygons. In EDA, intractable simply means a poor way of approaching the problem. So we use heuristics. What does that mean? It means that we give up trying to guarantee that our solution is optimal in return for finding something pretty good quickly. Or at least in a time the designer can cope with.

Like my sheet-metal punching traveling salesman solution.

Sign up for Sunday Brunch, the weekly Breakfast Bytes email.