Ordinary Skill in the Art
Based on the 2000 Knuth-Prize Lecture
Jeffrey D. Ullman
Nov. 16, 2000; minor updates Aug. 30, 2001
      Having worked down the hall from Don Knuth for over 20 years, it is plain to me how unworthy I am to receive an award named for him. Yet working at Stanford has given me the opportunity to see sides of Don that may not be obvious from reading his works. One aspect of Don Knuth that may not be obvious is that he has a thing about lawyers. He really hates lawyers --- so much so that when they call to ask him to serve as an expert witness in a case, he tells them his rate is $10,000,000 an hour.

      Usually, they then ask Don if he can recommend someone cheaper, and Don, knowing that I'll do anything for a buck, sometimes sends them to me. As a result, I've gotten involved in a number of interesting cases involving software patents, and over the years, I have come to the conclusion that:

      What is Patentable?

      Note: much of this section was explained to me by my son Peter, who is one of the first patent attorneys to have a degree in Computer Science. Until very recently, you could not even take the patent bar examination if your undergraduate degree was (only) in CS; you had to have engineering or a hard science degree, as well as a law degree.

      Patents have been awarded since 1790 to further the useful arts. Not technology or engineering, but ``arts.'' We should remember that Don Knuth viewed computer programming as an art --- surely a useful art --- long before anyone accepted the idea that software could be patented. In order for an idea to be patented, there are three tests that must be met:

      1. The idea must be ``novel.''

      2. The idea must be ``nonobvious.''

      3. The idea must be useful.

      The third of these is perhaps the easiest to tackle. Most algorithms and most programs meet the test of being useful. There is one subtlety, however. An algorithm, data structure, or other idea that we might see as evidently useful is not patentable in a form disembodied from any application. For example, we might instantly agree that binary search trees are a useful idea, but they could only be patented as part of an ``apparatus,'' e.g., a computer program, that did something useful, such as retrieve journal citations given a keyword.

      How about ``novel'' and ``nonobvious''? Aren't they synonyms? Not in the world of patents.

      It is interesting to observe that if you are on a program committee, these three criteria are exactly those you use to decide whether or not to accept the paper (although the typical FOCS/STOC program committee takes a longer and broader view of what is ``useful''). However, several tricky points come up when we try to understand what is ``obvious'' to a person of ordinary skill in the art. Among them:

      1. What is the scope of ``an art''? All computer science? A topic roughly equivalent to one course at the undergraduate level? The subject of a PhD thesis? One important criterion is that we must consider people actually practicing the art, not those thinking about the art. Thus, an academic researcher may not be a good, or even acceptable, model for a person of ordinary skill in the art. Apparently, a better model would be a person with a BS degree in Computer Science who writes code for a living. In some cases, e.g., a patent involving locking algorithms for database systems, we might take the proper model to be someone who had had an appropriate MS-level course, database systems in this example.

      2. How obvious is ``obvious''? If we posed the problem to 100 people skilled in the art, would all 100 have to come up with the solution that appears in the patent? Would 90 be enough? 50? 10? 1? More complex --- and quite germane to what I regard as a central problem of how patents are granted and enforced --- is the question of what happens if the 100 people come up with 10 or 100 different solutions, all or most of which are at least as good as the patented idea, and yet few if any are exactly that idea.

      The Purpose of Patents

      The intent of Congress in establishing patents is both to encourage inventors to invent, and to encourage them to share their knowledge with others. Sharing enables an invention to be used effectively, perhaps in many applications. Sharing also supports the ``stand on the shoulders of giants'' phenomenon --- one discovery can engender others, resulting in an upward spiral of technology.

      The reward to the inventor includes the right to receive fees for licensing the patent to anyone who would use the idea. But more important is limited-term freedom from competition. This protection has another beneficial side effect: it encourages the investment needed to bring a good idea to market. Without such protection, an investor would fear that others would steal whatever market they had developed with the new idea.

      Of course many of the best ideas have been put in the public domain, shared and made available to others without reward for the inventor (well maybe tenure, reputation, and the other pleasures of life as a research scientist). Reasonable people may disagree on the matter of reward for invention, yet we cannot deny that it has been effective. In a sense, Communism --- an intuitively appealing concept --- failed because it forgot that the best minds need to be motivated, and money works better than anything else, on average. My personal view is that it is great that R, S, and A were able to profit from a patent for a novel, nonobvious, and useful encryption scheme, but less wonderful that pharmaceutical companies are able to profit from their inventions to the extent that poor nations are dying of controllable HIV because they can't afford what the drug companies demand.

      What Goes Wrong?

      My experience concerning patents has convinced me that, at least in the area of software, there are significant abuses of the patent system. There are several forces involved that encourage abuses:

      1. Until recently, lawyers with computer-science degrees were not considered qualified for the patent bar, and patent examiners may have had difficulty getting into the mindset of the practicing programmer. It is unsurprising that patents can slip through without meeting the tests for patentability as a programmer would see them.

      2. Venture capitalists look for patents when deciding whether or not to invest in a startup. Thus, startups file patents regardless of whether or not the patent has any merit, or even whether it is likely to be granted. The result is that there are many wild claims floating around, and these patents are like land mines. If you don't know whether they will be upheld, there is great risk in using the ``idea.'' The reason is that the law penalizes violators of patents extensively, while there is no penalty for obtaining a patent that is eventually overturned. One of the most famous recent cases in point is Amazon's ``one-click shopping'' idea. Now I think Amazon deserves a lot of credit for pioneering work. Notice that Barnes-and-Noble could have become Amazon.com, but they didn't see how to do it until Jeff Bezos showed them. However, the one-click patent, although many say it is not going to stand up in court (you can see some examples of opinion with the Google query one-click patent), inhibits the use of the idea, or forces people to pay money that may not be justified (as Apple has done; I learned that from the same Google query). While one could argue that the patent system is here protecting an inventor, it is also possible that the system is preventing people from using an idea that is really in the public domain --- exactly the opposite of the support-of-technological-progress ideal of the patent system.

      3. In the absence of any true injury, companies with large ``patent portfolios'' will threaten smaller companies with lawsuits if they don't license their patents. I have seen cases where company A has had to pay company B, even though A did not get any value from the patents of B, having developed or obtained the ideas allegedly covered by B's patents quite independently of B. Indeed, it is probable that A could have won a court test, but because the risks are all on A's side, they prudently ``paid protection'' rather than risk having their house burned down.

      4. One sees even more egregious cases of individuals who file a patent, and later discover that their patent resembles something important that has happened --- no thanks to them --- such as spreadsheets or the Web. Having never made any attempt to publish their idea, usually because it is in fact unpublishable by the normal standards of our field, they start a suit against the people who are true innovators. Alas, because of the risks involved, it is often easier to pay protection than to fight a legitimate battle in court.

      Some Examples

      I would like to describe two instances of patent struggles in which I have been involved. Each illustrates some of the difficulties in preventing the granting and enforcement of questionable patents.

      1. The first is a case in which it was utterly transparent that the idea was not new, yet proving it not to be ``novel,'' as required by law, was tricky. Because it was so blatently obvious, no one had made a public declaration of the idea, as required for a legal conclusion of ``not novel.''

      2. The second illustrates what I believe to be a contradiction in the way nonobviousness is established. The method patented was one of many ways to solve the problem. I believe them to be collectively obvious, yet the jury decided that a patent on one method covered all other possible ways.

      A Patent on Triangular Matrices

      In 1956, Sidney Cabin, who was my math teacher and math-team coach at Van Buren High, was teaching the solution of simultaneous linear equations. I distinctly recall one day his pointing out that sometimes you got lucky. You might find one equation that involved only one variable, say x, and constants, so you could solve for x immediately. Then, you might find an equation that involved only x, constants, and some other variable y, so you could also solve for y. And then,... well you get the idea.

      Fast-forward to 1968. Two guys thought of the same idea, and somehow concluded that they were the first people ever to think of it. I guess they didn't have the benefit of a Van-Buren-High education. They filed a patent on the idea, in particular, as embedded in a computer program. Well you couldn't actually patent programs in those days, so it was described as a device that searched for an order of variables that made the matrix of the equations triangular. And then they added that you could also write a program to do this job.

      To the credit of the patent examiner, the patent was rejected. However, these guys were not inclined to give up. By the early 1980's they had gotten the court to overrule the Patent Office and grant them the patent. That was convenient timing, because by then spreadsheets were becoming popular, and they decided that all the spreadsheet manufacturers were violating their patent, since they in fact were filling in cells based on the values of previously computed cells.

      Enter a man whom we'll call Mr. P, standing for ``philanthropist.'' Mr. P was very generous to his community. For example, he received great public notice for offering to pay for the college education of every student to graduate from a certain ghetto school, and he apparently followed through on this offer, which was taken up by many of the students. The only trouble was that Mr. P had an odd way of making the money he gave away. He would buy up patents and then file lawsuits against any target with money. Given the risk/reward pattern associated with patents, he would usually receive a settlement, often a large settlement.

      So Mr. P bought the patent on triangularizing matrices for almost nothing and brought suit against the spreadsheet manufacturers. I was enlisted in their defense, and the attorneys decided that their best bet was to show that the idea was not novel; i.e., to find prior art in the literature. The trouble is that the idea is so obvious that no one could publish it in a journal or conference proceedings. It might have been written in Mr. Cabin's notes, but that is not a public disclosure of the idea, so it wouldn't count even if so.

      Well we looked and looked. I found something in Hilbert's writings on equational theories that might be interpreted as describing the solution to a triangular system. One of the other people on the team found a thesis from MIT in 1962 that solved the following problem. Suppose you are carrying a FORTRAN deck of cards and you drop them. You'd have a lot of trouble assembling them in the correct order, and if you don't, the program won't run. But if instead of FORTRAN you used a language that was in effect a triangular system of equations, then you could feed them into the hopper in any order, and another program could topologically sort them and the program would run.

      The denouement was less than spectacular. The judge threw the case out on a technicality. It was never decided that the patent itself was bogus and should never have been granted. But at least justice was, in its own weird way, served.

      Among the Many Ways to Compress Data

      The next story involves a small-but-rapidly-growing software company, which we'll call C. They implemented a file-compression algorithm that consisted of three things:

      1. The Lempel-Ziv algorithm, which you should recall involves storing strings that have appeared previously in the file and replacing subsequent occurrences of that string by pointers to the original occurrence. For instance, if the appears many times, we can save by replacing all but the first to a short pointer to the byte of the file where the first the occurs.

      2. An implementation of the dictionary data abstraction. Recall this abstraction, which I think is one of Don Knuth's neatest ideas, is a set with the methods ``insert,'' ``delete,'' and ``membership-test.'' The dictionary would hold the unique strings seen so far and their original locations in the file.

      3. Because this story takes place in the 1980's, the amount of main memory available was really tiny. Often a PC had 64K bytes, or less. Thus, they had to be careful not to store too many strings in the dictionary, or they would run out of main memory, and performance of the data-compression would drop.

      At this point, you should stop and think how you would solve this problem. That is, you need to pick some dictionary implementation, and modify it so that it will store only a limited number of strings, and yet give the correct answers to queries that ask whether a given string is in the set stored. Technically, you should think with the mind of someone from 1985, but I suspect that the method you come up with is likely to have been known in 1985, and moreover, taught to undergraduates of that year and well before.

      Anyway, back to our story. C was sued by a company we'll call D, which had a patent on the three steps that I outlined above. Well not exactly. They couldn't patent Lempel-Ziv, a nice idea that was in the public domain. They tried to patent the dictionary, but that wasn't going to hold up, since the abstraction is in Knuth's 1973 book. However, they also patented a particular method for solving the third problem: limiting the size of the dictionary.

      I have to be careful not to reveal too much detail, but let us say that one of C and D used a hash table with a limited number of elements per bucket, and the other used a binary search tree with a limited depth. D sued C for patent infringement, and I enlisted to defend C. At the trial, the jury learned more about the background of the case. Previously, C had licensed the software of D to include in its popular software product. Later, C decided to drop D's software and implement its own version. That decision was a disaster for D, and apparently the jury thought more about this aspect of the case than about the issue of whether or not the solution of D in the patent was or was not ``obvious.''

      In retrospect I should have been more careful about the implications of a decision in favor of C. Even though I believe, and will try to argue shortly, that the case reveals a logical flaw in the way patents are treated by the courts, I also feel that it is the responsibility of all in the scientific community to support the ethical handling of intellectual property.

      Problem 1: The Least Novel Ideas May be the Hardest to Refute

      The illustrations above point to two subtle flaws in the way software ideas are vetted for patentability. The first problem is that our literature takes a form rather different from that of most any other field in which patents are issued. For instance, advances in chemistry are normally published in journals, so if you want to know whether something is novel, you do a literature search.

      If you want to find a good idea in software, you can probably find that in the CS literature as well. But what about a bad, trivial, or blatently not-novel idea? You are unlikely to find that published, because program committees and journal referees reject such articles. Unlike most fields, software has a written repository outside the conventional literature: the software itself. Many mundane ideas appear in software; well-crafted software is often mundane. However, documents such as unpublished software are excluded as a proof that an idea is not novel, because the software itself is not a public document. As in the case of the patent on triangular matrices, it is often quite hard to find a public, written statement of the idea, giving the illusion to the court that the idea indeed may be novel.

      An interesting exploitation of this paradox is the Web site called BountyQuest (Added 12/28/07: this site no longer exists in the form I referred to.) There you will see published rewards for finding in the literature a document that represents prior art for some of the most notorious patents of obvious ideas, including the one-click patent. The people who have offered the rewards are probably safe. The reason, as stated above, is that no one would be able to publish the idea in a public place. (Added 2/7/01: Jim Ward of BountyQuest informed me that there had indeed been some prior art discovered and that they had awarded bounties to four winners.) More importantly, by diverting attention to the issue of novelty --- the nonexistence of a prior document describing the exact idea --- the sponsors of the bounty quest are able to ignore the true issue: the ideas are obvious, and something very much like it would be developed by anyone faced with the same challenge.

      Problem 2: It Is not Always Obvious What Is Obvious

      Now, let us turn to the problem raised by the data-compression example. My belief is that finding some way to limit the size of a dictionary is (and was, in 1985) well within the capability of the typical programmer with a BS degree in CS. In order to claim obviousness, however, we must do the thought experiment and imagine the typical programmer faced with this problem. My guess is that, while most would solve the problem somehow, they would come up with a large number of different solutions, including several hash-based solutions, tree-based solutions, and probably other methods as well.

      If the patent examiner believes that the result of such a hypothetical experiment is as I suggested above, then they are obliged to reject a claim such as ``any method for limiting the size of a dictionary during execution of the Lempel-Ziv algorithm.'' However, they should grant a patent on the actual method used.

      But when the case goes into court, something very different happens. A court will not necessarily allow one to circumvent a patent by achieving the same goal in a different way. In the data-compression case, changing the data structure completely was thought to be an equivalent implementation of the patented idea. Thus, we have the following paradox:

      What Can We Do About The Problem?

      There are a number of things that I wish would work, but won't. Among them:

      1. I'd love to see the standards of the program committee used to measure what was patentable. These standards include novelty and nonobviousness; they also include usefulness, although with perhaps a disagreement about the immediacy of use. It's not going to happen because:

      2. I'd love to see public review of patents before they are granted. It would be wonderful if responsible scientists regularly argued for the obviousness, or provided prior citations, for weak patents. The right of the inventor to keep ideas secret if they are not granted a patent makes this approach a nonstarter, as well.

      3. I'd love to see a requirement for the demonstration, along with every patent granted, of the superiority of the method. This criterion is implicit in the way we evaluate our own work. You can't just publish a paper saying ``here is how I would solve this problem''; you need a justification, such as being the only way known at the time (e.g., the RSA patent), or being provably faster, simpler, or more general than previously known methods. Surprisingly, there is nothing in patent law that requires a patented method to be good. Worse, because of the paradox regarding equivalence classes of methods, the patent on a bad method can turn out to cover a good method.

      But here are a few things I encourage you to try. First, although a professor of theoretical computer science is not a good model of a person practicing the art with ordinary skill, we are a large source of experts, and experts play an important role in the process of validating patents. Some of the arguments we need to mobilize in support of true innovations and against the bogus or trivial are: