||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
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
The patenting of algorithms and the software that embodies them leads to
inequities as often as it protects true innovation and genuine
The standards for innovation set by the CS Theory community should be
given more weight when deciding the validity of a software patent.
There should be an effort to educate the courts on the distinct nature
of innovation in computer software, and to help distinguish innovation
from wishful thinking or the fantasies of people who are unaware of the
state of knowledge.
What is Patentable?
Note: much of this section was explained to me by my son
who is one of the first patent attorneys to have a degree in Computer
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
In order for an idea to be patented, there are three tests that must be
The idea must be ``novel.''
The idea must be ``nonobvious.''
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
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.
An idea is novel if it does not appear in previous, public
An idea is nonobvious if it would not be discovered by one of
``ordinary skill in the art'' when the idea was needed.
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.
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.
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
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
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
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
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:
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.
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
One of the most famous recent cases in point is Amazon's ``one-click
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
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
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.
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.
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.
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
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.''
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
I distinctly recall one day his pointing out that sometimes you got
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
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
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
He would buy up patents and then file lawsuits against any target with
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
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
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
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.
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
The dictionary would hold the unique strings seen so far and their original
locations in the file.
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
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
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
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
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
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
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
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
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
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:
When deciding whether an idea is obvious, the existence of an
equivalence class of well-understood
solutions does not render all of them as a class
Yet when a patent on one method is granted, it de facto covers
all members of the class.
What Can We Do About The Problem?
There are a number of things that I wish would work, but won't.
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
It's not going to happen because:
Courts really like the jury system. The idea of substituting an elite
for random jurors, even in a specialized matter like patent validity,
scares many, including me.
Publication is an unfair requirement for the start of the
The reason is that, should a patent not be granted, you have the
right to keep the idea as a trade secret --- not protected by law, but
protected by your own best efforts.
Peter points out that anyone filing a patent outside the US will have
their application (not just the granted patent) made public after 18
Moreover, in the US, a year 2000 change also results in publication of
the application after 18 months, unless the inventor certifies
they will not file in any other country.
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.
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:
We should emphasize to the courts that
computer-science students are taught techniques, algorithms,
data structures, models, and so on, that are by their very nature
intended to be general.
They appear in an endless variety of applications, and it is within the
capability of the students we train -- those with ordinary skill in the
art --- to use the models, build the data structures, and implement the
algorithms when needed to solve a problem at hand.
To the extent that it is permitted by patent regulations regarding
public disclosure of applications and granted patents, the scientific
community can make its views known, as many pundits and
technology-oriented journalists do (to see some examples, try a Google
query like bogus
encourage the decision-makers, including Congress and the courts, to
resolve the paradox of equivalent implementations.
If you have any doubt that Computer Science is unusual, if not unique,
in the matter of multiplicity of intellectually equivalent solutions,
consider how difficult it is to convince non-Computer-Scientists that
two solutions to an introductory programming homework represent
People who do not understand the nature of CS tend to believe ``of
course they came up with the same program; you asked them to solve the
same problem, didn't you?''
My preference is that the existence of an equivalence class of solutions
should render them all obvious and unpatentable.
A weaker solution is to allow a patent on an approach that has not yet
appeared among the various ways to solve the problem, but not allow
that patent to escalate to a patent on all possible ways to solve the
same problem using the readily available tools of our trade.
further encourage decision makers to incorporate into software
patentability the requirement that the idea be a measurable improvement
on what is obvious.
Our field may be unique in that we have the tools to address ``better,''
and we should exploit that capability because it rewards true invention
while discouraging patents whose effect is to inhibit progress rather
than to further it.
We should search for ways to protect the true intellectual property of
an innovation, rather than using questionable ``inventions'' in the
software area to protect it.
As a case in point, I don't want to sound too negative about Amazon and
``one-click.'' Jeff Bezos appears to have discovered that book-selling
was the ``killer-app'' for eCommerce, and deserves the credit for a
Perhaps he even deserves protection for the idea, confining other
booksellers to their old ways of operation.
However, it strains credibility to argue that the mechanism for
protecting the on-line bookselling concept should rest with software
that was obvious once one is given the idea of selling on the Internet.
When choosing whether or not to support a case, we should examine the
It is tempting to enlist in whichever side asks you.
However, it does not benefit the field if legitimate inventors are
thwarted or if purposeful attempts to misuse the patent system for gain
are allowed to succeed.
A while ago, I decided that it made more sense to give URL's of
documents that appeared on the Web than to give conventional paper
Then, I began to realize that an even better approach to helping people
find relevant information was to give the Google query I used and let
people follow the same query, perhaps to more up-to-date information.
You can find patents on-line through the Web site of the US Patent Office.
For the story of the patent on triangular matrices, you can read the Court's Decision.
Or, go to Google with the query refac spreadsheet
to find a
variety of opinions about the case.
Refac is the name of the company ``Mr. P'' runs to exploit patents.
Here is the story of the Data Compression
You can also find more with the Google query microsoft
And for a good 'ol hardcopy citation, The Digital Dilemma,
National Research Council report, National Academy Press, 2000 has a
discussion of the history of software patents, pp. 192ff.
Added later: The Slashdot
discussion of the article.
Added 8/30/01: There is an interesting proposal to make big-oh
complexity a fundamental component of software patentability.
The Article by Andrew