Count EFF In
David Farber
Lots of folks have been working on that issue .. patent research.
There is the Software Patent foundation etc. In that case
too many ...
As to fighting patents and making it damn uncomfortable
for companies to continue to pursue enforcement of
such patents, the payoffs have been very very good lately
David Farber; Moore Prof. of Telecom, U of Penn, Philadelphia, PA 19104-6389
Member of the Boards of EFF and ISOC. Join EFF! send mail to e...@eff.org
Seth Finkelstein
>In article <3eknhi$3...@infonaut.com> jf...@infonaut.com (Jim Freeman) writes:
>
>>One could argue that the
>>root cause of this debate is that some people feel that patenting software
>>flies in the face of the express purpose of the patent system, and that
>>the hullabaloo about this is simply a symptom (not the root cause).
>
>I suppose some people might actually feel thisway . I'd be interested in
>hearing what their basis for feeling so is.
There is much material explaining this position in the archives
of the League for Programming Freedom. Just ftp to prep.ai.mit.edu,
cd to /pub/lpf
>I have serious doubts that it would be anything I'd consider terribly logical.
From the README:
The file techrev.patent is an article by Brian Kahin on the dangers of
software patents, published in Technology Review (March 1990).
>After all, the patent
>system--as with other forms of intellectual property--has the express purpose
>of encouraging creation and innovation. Just what is it about patenting
>algorithms that "flies in the face" of that purpose anymoreso than
>patenting other technical creations?
The articles and other material explain this in great detail.
Having to search - and work around, or license, the tremendous number of
concepts that go into many programs can be a severe burden.
>As far as I have seen to this point, the most reasonable complaints
>regarding algorithm patents are pragmatic ones--primarily involving the
>traditional inexperience of the patent examiners when it comes to algorithms,
>and the lack of a comprehensive catalog of prior art. Such pragmatic
>concerns, of course, say nothing to support a contention that protection
>for algorithms is inimical to the patent system.
Those complaints are the most common, because that's the first
line of trouble. A second line - licensing issues, applied to actual
existing programs - is what we are seeing now. Before, it was mostly a
theoretical, what-could-happen, objection. Now we are seeing cases in
progress, and more negative effects are becoming evident. Just imagine if
Unisys decided to prosecute everyone with a GIF viewer ...
--
Seth Finkelstein se...@mit.edu
Disclaimer : I am not the Lorax. I speak only for myself.
(and certainly not for Project Athena, MIT, or anyone else).
Jefferson Ogata
> There is much material explaining this position in the archives
>of the League for Programming Freedom. Just ftp to prep.ai.mit.edu,
>cd to /pub/lpf
>
> The file techrev.patent is an article by Brian Kahin on the dangers of
> software patents, published in Technology Review (March 1990).
This thread may be drifting off some of the newsgroups it is going
out on...feel free to edit the Newsgroups: line if you follow up.
I was just reading Brian Kahin's techrev.paper on prep.ai.mit.edu
and found it very interesting. The following thoughts occurred to
me that I didn't see him address, and I was curious what people
thought about them. These are just my opinions based primarily on
the information in Kahin's paper (hope I'm not overstepping any
bounds ;^), as I know very little about patent law.
It seems to me that the main problem with software patents is the
17-year lifespan. 17 years in the development of physical processes
is a reasonable time for growth of an industry. But scaled to the
high rate of development in the software industry, it is more like
centuries. Perhaps a shorter lifespan (e.g. 1.5 years from the time
of granting) would allow inventors to capitalize on moderate or
radical innovation in software design, while not hamstringing the
industry.
The industry that stands to benefit the most in the near term from
software patents is the legal profession. Having to hire lawyers
for patent searches as a part of software development is going to
provide a continuous and high level of income to legal firms. In
fact, the streamlining of the patent search process could result
in the development of a whole new industry. ;^)
--
Jefferson Ogata og...@netcom.com
"Animals without backbones hid from each other or fell down. Clamasaurs and
oysterettes appeared as appetizers. Then came the sponges, which sucked up
about ten percent of all life." - Firesign Theatre
J. S. Greenfield
>>After all, the patent
>>system--as with other forms of intellectual property--has the express purpose
>>of encouraging creation and innovation. Just what is it about patenting
>>algorithms that "flies in the face" of that purpose anymoreso than
>>patenting other technical creations?
>
> The articles and other material explain this in great detail.
>Having to search - and work around, or license, the tremendous number of
>concepts that go into many programs can be a severe burden.
I still can't see how this "flies in the face" of the purpose of the patent
system. Inventors of non-algorithmic processes must also search the prior
art for potential infringements.
How is this philosophically different int he case of algorithms, to the extent
that patent protection for algorithms "flies in the face" of the purpose of
the patent system?
It seems to me that algorithm patents serve the same purpose as non-lagorithm
patents--to encourage the creation and *sharing* of technical knowledge.
Remember that, in the absence of patent protection, a creator who wishes
to protect his invention is left only with trade secret protection.
Note--I'm not making an argument for or against any kind of patent here. I'm
merely arguing that there is no substantive philosophical difference between
patents for algorithms and non-lagorithmic processes--and certainly no
such difference that supports a claim that patent protection for algorithms
"flies in the face" of the purpose of the patent system.
It still seems apparent to me that the real problem with patent system
vis-a-vis algorithms is the lack of a comprehensive catalog of prior art
and inexperience by the examiners, leading to the granting of patents for
algorithms that aren't sufficiently original to warrant such protection.
>>As far as I have seen to this point, the most reasonable complaints
>>regarding algorithm patents are pragmatic ones--primarily involving the
>>traditional inexperience of the patent examiners when it comes to algorithms,
>>and the lack of a comprehensive catalog of prior art. Such pragmatic
>>concerns, of course, say nothing to support a contention that protection
>>for algorithms is inimical to the patent system.
>
> Those complaints are the most common, because that's the first
>line of trouble. A second line - licensing issues, applied to actual
>existing programs - is what we are seeing now. Before, it was mostly a
>theoretical, what-could-happen, objection. Now we are seeing cases in
>progress, and more negative effects are becoming evident. Just imagine if
>Unisys decided to prosecute everyone with a GIF viewer ...
I don't see how this is a "second line." The complaints about the LZW patent
generally take one of two forms: 1) the algorithm was known long before the
patent was applied for, or 2) the algorithm isn't sufficiently inoovative
to warrant patent protection. I can't factually comment on either claim.
However, if either were correct, the granting of the patent would be a problem
falling into the class of practical problems I described.
As far as Unisys' current action goes, its a different issue entirely, and
there are serious doubts in my mind as to whether Unisys could prevail in
any action. The problem with the current action is not at all specific
to patents. The problem is that Unisys (apparently) did little to nothing
to enforce its patent (at least as used in GIF algorithms) for a good eight
years or so. That has caused many people to rely on Unisys' non-enforcement.
It seems highly unlikely that Unisys can, years later, successfully enjoin
such uses, or collect damages. (That is, prevail in court. We all know the
realities/intimidation of litigation.)
--
J. S. Greenfield gre...@thelair.zynet.com
(So what were you expecting?
A Gorilla?!) "What's the difference between an orange?"
J. S. Greenfield
>It seems to me that the main problem with software patents is the
>17-year lifespan. 17 years in the development of physical processes
>is a reasonable time for growth of an industry. But scaled to the
>high rate of development in the software industry, it is more like
>centuries. Perhaps a shorter lifespan (e.g. 1.5 years from the time
>of granting) would allow inventors to capitalize on moderate or
>radical innovation in software design, while not hamstringing the
>industry.
First of all, I doubt that we can reasonably generalize *all* non-algorithmic
processes as being suitable for a 17-year life span. We certainly can't do
so for algorithms. Take the well-known RSA patent. How long did it take
for that patent to become at all profitable?
In any case, a 1.5 year lifespan is most assuredly useless. For one thing, it
takes years just to get a patent. If the true useful life span of a patent
is only 1.5 years, that lifespan will be over before patent protection is
granted. During that time, *anybody* will be able to use the algorithm
royalty-free.
The result would be that inventors would simply maintain new algorithms as
trade secrets. It would be the only way to protect the value of the
invention. Now *that* would fly in the face of the purpose of the patent
system, since the whole point of that system is to encourage the *sharing*
of knowledge, in order to advance technology...
J. S. Greenfield
>One could argue that the
>root cause of this debate is that some people feel that patenting software
>flies in the face of the express purpose of the patent system, and that
>the hullabaloo about this is simply a symptom (not the root cause).
I suppose some people might actually feel thisway . I'd be interested in
hearing what their basis for feeling so is. I have serious doubts that
it would be anything I'd consider terribly logical. After all, the patent
system--as with other forms of intellectual property--has the express purpose
of encouraging creation and innovation. Just what is it about patenting
algorithms that "flies in the face" of that purpose anymoreso than
patenting other technical creations?
As far as I have seen to this point, the most reasonable complaints
regarding algorithm patents are pragmatic ones--primarily involving the
traditional inexperience of the patent examiners when it comes to algorithms,
and the lack of a comprehensive catalog of prior art. Such pragmatic
concerns, of course, say nothing to support a contention that protection
for algorithms is inimical to the patent system.
Shari Steele
> The EFF/LPF could assist this process with some legal savvy
> in suggesting which versions (or portions thereof) of the
> extant GIF standards can be used without encumbrance.
> This would be the "Legal Issues Group" (LIG). They could
> also be a site for collecting some funds for reimbursing
> project participants for pizza, Chinese food, long-distance
> phone calls, and other tangible costs incurred up through Jan 10.
> Let me know who winds up doing this, and I'll cough up $50.
> Content and tools providers with vested interest and a lot to
> lose might want to be a good bit more generous than that.
EFF would be happy to find and work with competent pro bono legal counsel
to help with this (since none of us are patent attorneys per se and we want
to make sure we do this right). Not only are we willing to collect funds
for reimbursing project participants for the necessary pizza and jolt
expenses -- we will match all funds we collect, up to $1000, and throw in
EFF memberships to each person donating more than $100. Any funds that are
not used for this purpose will be saved in an account that is earmarked for
fighting future net threats only.
Go for it!
Shari
----------------------------------------------------------------------------
Shari Steele, Director of Legal Services sst...@eff.org
Electronic Frontier Foundation 202/861-7700 (voice)
1667 K Street, N.W., Suite 801 202/861-1258 (fax)
Washington, DC 20006-1605 202/861-1224 (BBS)
Keith Stone
wrote:
> EFF would be happy to find and work with competent pro bono legal counsel
> to help with this (since none of us are patent attorneys per se and we want
> to make sure we do this right). Not only are we willing to collect funds
> for reimbursing project participants for the necessary pizza and jolt
> expenses -- we will match all funds we collect, up to $1000, and throw in
> EFF memberships to each person donating more than $100. Any funds that are
> not used for this purpose will be saved in an account that is earmarked for
> fighting future net threats only.
Actually, if EFF wanted to do something REALLY contructive, they would
help work out a method to speed research for patent research. The root
cause of this debate is that Compuserve inadvertantly released into the
public domain a file format that required the use of a patented algorithm
do create.
Fighting an existing patent is a waste of time and money, since they've
already established a precedent for licencing the technology.
--
--------- Keith Stone | Voice: (910) 777-0511
|\\\ ///| Crewstone Consulting ltd. | FAX: (910) 777-1191
|/// \\\| 1001 South Marshall Suite 118 | "Beware of geeks bearing
--------- Winston-Salem, NC 27101 | GIFs"
Jim Freeman
Keith Stone <kst...@crewstone.com> wrote:
...
>Actually, if EFF wanted to do something REALLY contructive, they would
>help work out a method to speed research for patent research. The root
>cause of this debate is that Compuserve inadvertantly released into the
>public domain a file format that required the use of a patented algorithm
>do create.
Since that's not what they choose to do, it is probable the EFF does not
agree that this would be REALLY contructive. One could argue that the
root cause of this debate is that some people feel that patenting software
flies in the face of the express purpose of the patent system, and that
the hullabaloo about this is simply a symptom (not the root cause).
>Fighting an existing patent is a waste of time and money, since they've
>already established a precedent for licencing the technology.
No need to fight the patent - just make it irrelevant, work around it
without infringing - innovate instead of litigate.
...jfree
Daniel F Boyd
J. S. Greenfield <gre...@lanl.gov> wrote:
> The result would be that inventors would simply maintain new algorithms as
> trade secrets.
That would be a preferred result, as independent reinvention is
commonplace for software.
Lance Purple
>> The result would be that inventors would simply maintain new algorithms as
>> trade secrets.
Daniel F Boyd <bo...@cs.Buffalo.EDU> wrote:
>That would be a preferred result, as independent reinvention is
>commonplace for software.
How about the following: in order to get a patent, inventors must prove
they have maintained a trade secret for 5 years or so, without anyone
else independently discovering the invention.
That way, you wouldn't have so many patents on obvious inventions,
but you would get the original intended benefit of patents (the
invention isn't lost forever if the inventor dies, and the inventor
has incentive to put it into the public domain after recovering
the initial R+D costs).
L. Purple (lpu...@netcom.com)
J. S. Greenfield
>> The result would be that inventors would simply maintain new algorithms as
>> trade secrets.
>
>That would be a preferred result, as independent reinvention is
>commonplace for software.
That's not a preferred result. Patents are not supposed to be granted for
inventions that are fairly obvious to one skilled in the art. If an algorithm
is likely to be independently reinvented on a frequent basis, it ought not
receive a patent.
So the real issue there is the skill of the examiner in being able to
distinguish between the mundane and the truly innovative.
Quite clearly, there are some algorithms that are very *unlikely* to be
independently reinvented on a frequent basis. I certainly wouldn't expect
very many programmers to independently reinvent the Cooley-Tukey FFT, or the
RSA cryptosystem, for example.
In any case, the problem of independent reinvention is by no means peculiar
to algorithms. It exists for *all* forms of invention.
I have heard arguments that independent reinvention is more likely for
algorithms than for other forms of technology, merely because of the large
number of programmers. That may well be true, but even if it is, that
merely suggests to me that we might need a higher standard for what
constitutes a patentable algorithm. (Certainly, it ought to be higher than
the one currently in effect, due to fairly inexperienced examiners...)
David L. Elliott
>
>
>Quite clearly, there are some algorithms that are very *unlikely* to be
>independently reinvented on a frequent basis. I certainly wouldn't expect
>very many programmers to independently reinvent the Cooley-Tukey FFT, or the
>RSA cryptosystem, for example.
>
>
>In any case, the problem of independent reinvention is by no means peculiar
>to algorithms. It exists for *all* forms of invention.
>
>I have heard arguments that independent reinvention is more likely for
>algorithms than for other forms of technology, merely because of the large
>number of programmers. That may well be true, but even if it is, that
>merely suggests to me that we might need a higher standard for what
>constitutes a patentable algorithm. (Certainly, it ought to be higher than
>the one currently in effect, due to fairly inexperienced examiners...)
>
>
>--
>J. S. Greenfield gre...@thelair.zynet.com
A small correction... the FFT was discovered independently four times; once
as a way of designing synthetic-aperture antennas, the other times as
algorithms. Cooley and Tukey deserve great credit for the version we now have.
David
--
David L. Elliott dell...@src.umd.edu
Institute for Systems Research/ A.V. Williams Building
University of Maryland/ College Park, MD 20742
merlin
>17-year lifespan. 17 years in the development of physical processes
>is a reasonable time for growth of an industry. But scaled to the
>high rate of development in the software industry, it is more like
>centuries.
This isn't a unique problem for the software industry. Biotechnology
technology also develops at an extremely rapid rate. Without a doubt
there are many other rapidly developing industries experiencing these
problems.
Perhaps more important than the inconvenience of individual patents on
software development -- there is a serious problem when huge numbers of
patents are issued (as in biotechnology) which actually inhibit progress
and development of innovation in the field. This is contrary to stated
intent in the US Constitution that patents only be granted which advance
the state of the art by bring private innovation into public limelight.
Tim Smith
>>of encouraging creation and innovation. Just what is it about patenting
>>algorithms that "flies in the face" of that purpose anymoreso than
>>patenting other technical creations?
>
>Having to search - and work around, or license, the tremendous number of
>concepts that go into many programs can be a severe burden.
And how is this different from any other field in which things are patented?
--Tim Smith
Seth Finkelstein
In a line, there are big problems in scale and scope. In this
whole discussion, I keep getting the feeling that some people are asking
"What's the difference between a pack of a tigers and a housecat?
After all, we have well-defined procedures for the keeping of "cats",
and so we live with "felines" all the time. In fact, that old lady down
the block has a dozens housecats as pets, and the only injuries have
been a few scratchs. So why should it be any less safe to have a pack of
tigers roaming around the neighborhood? Isn't what people are concerned
about really just "nasty dispositions"? Of course there are some cats
which have gone feral, the problem is then not the system of feline
pets, but the underfunding and quality of animal control officers. What
is this illogical argument about having a pet tiger pack flying in the
face of the "pet system"? ".
Bob Cousins
>In article <1995010620...@eff.org>, sst...@eff.org (Shari Steele)
>wrote:
>
>> EFF would be happy to find and work with competent pro bono legal counsel
>> to help with this (since none of us are patent attorneys per se and we want
>> to make sure we do this right). Not only are we willing to collect funds
>> for reimbursing project participants for the necessary pizza and jolt
>> expenses -- we will match all funds we collect, up to $1000, and throw in
>> EFF memberships to each person donating more than $100. Any funds that are
>> not used for this purpose will be saved in an account that is earmarked for
>> fighting future net threats only.
>
>Actually, if EFF wanted to do something REALLY contructive, they would
>help work out a method to speed research for patent research. The root
>cause of this debate is that Compuserve inadvertantly released into the
>public domain a file format that required the use of a patented algorithm
>do create.
They wouldn't be called the EFF if they followed goals counter to their aim.
If you want to do something constructive Keith, why don't *you* set up
an organisation for patent research, and see how much support you get -
from people like Unisys, IBM, patent lawyers...
Regards,
--
Bob Cousins, Sirius Cybernetics Ltd.
Say No to GIF tax - say Yes to GEF!
Keith Stone
>
> No need to fight the patent - just make it irrelevant, work around it
> without infringing - innovate instead of litigate.
Agreed. If developers feel the LZW license is more trouble than it's
worth, an alternative will result. If folks find that the cost of LZW is
less than the hassle of creating an alternative, that's fine too. In
either case, the issue is resolved without boycotts, mail-bombing, and
lawsuits.
My real concern is that patent research is a pain in the butt, and more of
these flaps are going to crop up. Since patents are a way of life, it
seems more productive (to me at least) to solve the issue up front than to
wait for an eruption and get out a fleet of lawyers.
Keith Stone
Greenfield) wrote:
> As far as Unisys' current action goes, its a different issue entirely, and
> there are serious doubts in my mind as to whether Unisys could prevail in
> any action. The problem with the current action is not at all specific
> to patents. The problem is that Unisys (apparently) did little to nothing
> to enforce its patent (at least as used in GIF algorithms) for a good eight
> years or so. That has caused many people to rely on Unisys' non-enforcement.
> It seems highly unlikely that Unisys can, years later, successfully enjoin
> such uses, or collect damages. (That is, prevail in court. We all know the
> realities/intimidation of litigation.)
According to Unisys, they have over 100 existing LZW licenses in effect.
To me, that shows they are enforcing their patent. I know they were
licensing it at least five years ago in software, since I taked with then
at that time about using it. We did not license it becasue the product
didn't get off the ground, but went far enough to know that both one time
fees and usage based royalties were available.
Unisys wouldn't have found out about GIF until AFTER if became popular.
When it first came out, both GIF and Compuserve weren't even on their
radar screen. Even in graphics circles, I bet only developers knew of LZW
being in the GIF format. Most others didn't know or care.
Jurgen Botz
>inventions that are fairly obvious to one skilled in the art. If an algorithm
>is likely to be independently reinvented on a frequent basis, it ought not
>receive a patent.
Right. The problem is, they *are* being granted for algorithms that
are "fairly obvious". Constantly. Because patent examiners have no
clue about what's obvious and what's not. And because there are *lots*
of smart people out there working on software and to whom you could go
and say "invent me an algorithm that's a bit like LZ, but better" and
by tomorrow they'll have LZW. But if you look through a bunch of software
patents you'll find that things like LZW and RSA are the exceptions in
that they're really relatively clever... most software patents are issued
on stuff a smart high-school student would come up with immediately if
you asked her to solve the same problem.
The hard thing about writing software isn't algorithms. It's
intelligent design, code structuring, thorough testing, etc. 99% of
software packages out there use only algorithms that are "fairly
obvious" and which were "invented" by the programmers as they were
coding without even thinking about whether this might be something
someone else has already "invented".
And as I said elsewhere recently, a lot of these patented "algorithms"
aren't even what a real programmer would call an "algorithm" but more
like a protocol or a functional spec (i.e. Hayes "escape guard time",
Compton's "multimedia", the network-byte order thing, the list is
endless).
This situation *CANNOT* be corrected easily... you'd have to make some
of the best computer scientists patent examiners before you'd even have
a chance at issuing *reasonable* patents on algorithms, and that just
isn't going to happen.
J. S. Greenfield
>>Quite clearly, there are some algorithms that are very *unlikely* to be
>>independently reinvented on a frequent basis. I certainly wouldn't expect
>>very many programmers to independently reinvent the Cooley-Tukey FFT, or the
>>RSA cryptosystem, for example.
>A small correction... the FFT was discovered independently four times; once
>as a way of designing synthetic-aperture antennas, the other times as
>algorithms. Cooley and Tukey deserve great credit for the version we now have.
I'm not sure what you mean by "correction." I don't think that four
independent re-discoveries contradict my suggestion that we wouldn't expect
such re-discoveries to be "frequent."
--
J. S. Greenfield gre...@thelair.zynet.com
J. S. Greenfield
>>> The articles and other material explain this in great detail.
>>>Having to search - and work around, or license, the tremendous number of
>>>concepts that go into many programs can be a severe burden.
>>
>>And how is this different from any other field in which things are patented?
> In a line, there are big problems in scale and scope. In this
>whole discussion, I keep getting the feeling that some people are asking
>"What's the difference between a pack of a tigers and a housecat?
>After all, we have well-defined procedures for the keeping of "cats",
>and so we live with "felines" all the time. In fact, that old lady down
>the block has a dozens housecats as pets, and the only injuries have
>been a few scratchs. So why should it be any less safe to have a pack of
>tigers roaming around the neighborhood? Isn't what people are concerned
>about really just "nasty dispositions"? Of course there are some cats
>which have gone feral, the problem is then not the system of feline
>pets, but the underfunding and quality of animal control officers. What
>is this illogical argument about having a pet tiger pack flying in the
>face of the "pet system"? ".
I'm unconvinced that your analogy is particularly meaningful. It's fine
to draw analogies, but when the main issue is--as you say--scale and scope,
analogies are relatively useless, since these analogies are drawn precisely
to *exaggerate* the scale and scope of the problem.
And let's remember, the original claim to which I object (and to which I still
do object) was the claim that algorithm patents flew int he face of the
*purpose* of the patent system.
We have yet to see anybody present a credible argument as to how patenting
algorithms is, at a philosophical level, inimical to the patent system's
primary purpose of encouraging innovation and the *sharing* of the technical
knowledge derived from such.
In any case, for those of you who maintain that the patent system is generally
reasonable, but that algorithm patents are inherently bad, please reconcile
the following apparent inconsistency:
In such a patent system, one can patent a circuit that implements (in hardware)
an innovative algorithm. However, the same algorithm is ineligible for
patent protection, if implemented in software.
Just what justification is there for having such an arbitrary distinction
between hardware and software implementations?
In the course of this discussion, I've come to a tentative hypothesis that
explains the fairly widespread support for this arbitrary distinction. It's
quite simple. Lots of people (particularly those on the net) have easy access
to computers--either to program themselves, or to use (free or cheap) software
from others. Consequently, those people tend to feel far more restricted
by the idea of an algorithm being protected by patent, than by hardware
patents. Most of them aren't about to go out and build their own hardware.
I suspect that if everybody had easy access to build circuits, and less
access to developing software, we'd be seeing arguments about how circuit
patents are evil, terrible, hideous things...
--
J. S. Greenfield gre...@thelair.zynet.com
(So what were you expecting?
A Gorilla?!) "What's the difference between an orange?"
J. S. Greenfield
>>Actually, if EFF wanted to do something REALLY contructive, they would
>>help work out a method to speed research for patent research. The root
>>cause of this debate is that Compuserve inadvertantly released into the
>>public domain a file format that required the use of a patented algorithm
>>do create.
>They wouldn't be called the EFF if they followed goals counter to their aim.
>If you want to do something constructive Keith, why don't *you* set up
>an organisation for patent research, and see how much support you get -
>from people like Unisys, IBM, patent lawyers...
This past year, didn't IBM offer to provide the PTO with a catalog of
algorithms, to be used for prior art searches by examiners? Companies like
IBM are *extremely* concerned about patents being granted for algorithms
that they have been using for years, and the potentially legal problems
that would arise from such.
J. S. Greenfield
>According to Unisys, they have over 100 existing LZW licenses in effect.
>To me, that shows they are enforcing their patent. I know they were
>licensing it at least five years ago in software, since I taked with then
>at that time about using it. We did not license it becasue the product
>didn't get off the ground, but went far enough to know that both one time
>fees and usage based royalties were available.
My comments were explicitly directed at enforcement against GIF algorithms,
which as far as I can tell from what I have seen so far, was essentially
non-existant. It is irrelevant whether Unisys enforced the patent
against others.
>Unisys wouldn't have found out about GIF until AFTER if became popular.
>When it first came out, both GIF and Compuserve weren't even on their
>radar screen. Even in graphics circles, I bet only developers knew of LZW
>being in the GIF format. Most others didn't know or care.
It's inconceivable to me that Unisys did not know--or even suspect the
possibility--that GIF compression was using LZW. It's been a public standard
for at least 8 years, and has seen widespread use.
I seriously doubt that Unisys could make a successful argument against
estoppel on the basis that it "didn't know" an infringement was occuring.
J. S. Greenfield
>>That's not a preferred result. Patents are not supposed to be granted for
>>inventions that are fairly obvious to one skilled in the art. If an algorithm
>>is likely to be independently reinvented on a frequent basis, it ought not
>>receive a patent.
>
>Right. The problem is, they *are* being granted for algorithms that
>are "fairly obvious". Constantly. Because patent examiners have no
>clue about what's obvious and what's not. And because there are *lots*
>of smart people out there working on software and to whom you could go
>and say "invent me an algorithm that's a bit like LZ, but better" and
>by tomorrow they'll have LZW. But if you look through a bunch of software
>patents you'll find that things like LZW and RSA are the exceptions in
>that they're really relatively clever... most software patents are issued
>on stuff a smart high-school student would come up with immediately if
>you asked her to solve the same problem.
>
>The hard thing about writing software isn't algorithms. It's
>intelligent design, code structuring, thorough testing, etc. 99% of
>software packages out there use only algorithms that are "fairly
>obvious" and which were "invented" by the programmers as they were
>coding without even thinking about whether this might be something
>someone else has already "invented".
I think a lot of algorithms people--including myself--would disagree with
you. Many algorithms are not trivial to develop, as you seem to suggest.
And history would seem to contradict you, also. How many researchers are
know for an algorithm they developed? How many researchers are known for
software engineering techniques? You will almost certainly find many, many
more of the former than of the latter...
(And that's not to disparage software engineering. I currently work
primarily in that area, and I did my dissertation work in that area.)
>This situation *CANNOT* be corrected easily... you'd have to make some
>of the best computer scientists patent examiners before you'd even have
>a chance at issuing *reasonable* patents on algorithms, and that just
>isn't going to happen.
You contradict yourself. First, you say that algorithms that are patented--
even the really good ones--could be developed overnight by "lots of smart
people," most even by high school students. Then you claim that the patent
examiner problem can *never* be solved without making the very *best*
computer scientists examiners.
Which is it? Are these algorithms so trivial that lots of smart people
could invent them overnight, or are the algorithms so complex that only
the very best computer scientists could serve as competent examiners?
It's inconceivable to me that *both* could be true.
In fact, I don't even believe that *either* is true. I believe that mere
mortals can be experienced enough to recognize algorithms that they, and most
others, would not trivially develop. I believe that it is unfair to judge
the performance of "mortal" examiners who are appropriately *trained*, on
the basis of the performance of examiners who are *not* trained in the
field of computer science.
(Remember, it was not until last year that the PTO decided to, experimentally,
hire some examiners whose backgrounds were in computer science. They still
have not made computer science a field which qualifies for the patent bar.)
Michael I Bushnell
Two people can start up a software company with about $30,000 capital
and produce major profit, if they are talented programmers. Their new
system might easily infringe hundreds of patents; they would have to
search patent databases for thousands of possibly patented algorithms.
Each patent search costs between $100 and $1000.
Other industries have *many* fewer "inventions" per product, and
*vastly* higher capital costs. For example, a car might only involve
a few dozen patents. On the other hand, starting a car company
requires tens or perhaps hundreds of millions of dollars in capital.
So software has the combination of vastly more "inventions" per
product and vastly lower intrinsic startup cost. See the difference?
--
Michael I. Bushnell |
+1 617 253 8568 -+-
m...@gnu.ai.mit.edu |
|
denryan@interaccess
: I think a lot of algorithms people--including myself--would disagree with
: you. Many algorithms are not trivial to develop, as you seem to suggest.
: And history would seem to contradict you, also. How many researchers are
: know for an algorithm they developed? How many researchers are known for
: software engineering techniques? You will almost certainly find many, many
: more of the former than of the latter..
Hmmmm, yes, the XOR algorithm was certainly a puzzler, stumping the
best minds in computer science for decades before a patented solution
turned up ........
"How many researchers are known for an algorithm (that) they developed?"?
R.E. Tarjan,
and of course the "Fundamental Algorist", Donald Knuth.
My God! To just think about the patents that Knuth could rightfully
claim beggars the imagination! And of how many of the current "software
patents" are constructed upon the freely available work of his!
In fact, I would conjecture that between Knuth and Tarjan, the entirety
of current "software patentry" is moot.
Jurgen Botz
>you. Many algorithms are not trivial to develop, as you seem to suggest.
Maybe many are not, but many are. In any case what I was saying was that
most *software* only uses trivial algorithms.
>And history would seem to contradict you, also. How many researchers are
>know for an algorithm they developed?
Hmm... yeah, tell me, how many are?
>How many researchers are known for
>software engineering techniques? You will almost certainly find many, many
>more of the former than of the latter...
Software engineering *techniques* are of highly academic interest and
there isn't so much of a sharp boundary between them. But look at
software packages... a lot more people are known for the excellent
software packages (incorporating good SE technique) they wrote than
are known for developing important algorithms. And a lot of that
software incorporates only algorithms that the programmers made up
on the spot, not looked up in the literature.
>You contradict yourself. First, you say that algorithms that are patented--
>even the really good ones--could be developed overnight by "lots of smart
>people," most even by high school students. Then you claim that the patent
>examiner problem can *never* be solved without making the very *best*
>computer scientists examiners.
>
>Which is it? Are these algorithms so trivial that lots of smart people
>could invent them overnight, or are the algorithms so complex that only
>the very best computer scientists could serve as competent examiners?
>
>It's inconceivable to me that *both* could be true.
It seems not only conceivable, but obvious to me that both are true.
Many (or most) algorithms are trivial, but whether this is true for a
particular algorithm is very hard to decide. Since you say that
you're an algorithms person, you should know that coming up with a
good algorithm is often as much a matter of intuition and luck as it
is skill... unlike many other engineering tasks it can't be easily
broken down into steps that can be refined until you have the best
possible outcome. Two equally good computer scientists can look at a
problem and after a night's work one might say "hmmm... this seems
hard... I don't think you can do it in better than O(n^2) time" and
the other looks at it and after fiddeling with ideas for an hour yells
"Heureka! I can do it in linear time!". But until you've made the
breakthrough you just don't know! Is it hard? Isn't it?
So what I'm saying is that a patent examiner might look at a patent
claim and ask themselves "could I develop this given problem X?" But
even if they are decent computer scientists, just because they can't
come up with a solution right then doesn't mean that 100 other people
(including aforementioned high-school students) couldn't solve the
problem overnight! Until you've solved the problem yourself you can't
really know how hard it is. Therefor the patent examiners have to be
so good that they could, on their own, come up with *all* the
solutions for which patent claims are filed. (But then we should just
leave them working in research labs cranking out algorithms to really
hard problems rather than shuffeling patent claims.)
>In fact, I don't even believe that *either* is true. I believe that mere
>mortals can be experienced enough to recognize algorithms that they, and most
>others, would not trivially develop.
And I disagree. There probably are a number of algorithms that any
reasonably well-trained computer sciencist could look at and say, "wow,
this is hard... I don't think many people could come up with this." But
most of the algorithms I've studied do not fall into this category. Until
you've tried to solve it for a while and failed, it's hard to say "this is
hard."
Henry Baker
Greenfield) wrote:
> In article <3enu5n$m...@newra.src.umd.edu> dell...@Glue.umd.edu (David
L. Elliott) writes:
>
> >>Quite clearly, there are some algorithms that are very *unlikely* to be
> >>independently reinvented on a frequent basis. I certainly wouldn't expect
> >>very many programmers to independently reinvent the Cooley-Tukey FFT, or the
> >>RSA cryptosystem, for example.
>
> >A small correction... the FFT was discovered independently four times; once
> >as a way of designing synthetic-aperture antennas, the other times as
> >algorithms. Cooley and Tukey deserve great credit for the version we
now have.
>
> I'm not sure what you mean by "correction." I don't think that four
> independent re-discoveries contradict my suggestion that we wouldn't expect
> such re-discoveries to be "frequent."
Maybe FFT is pretty obvious after all. Have you ever taken a CS algorithms
course? Nearly the entire course is concerned with converting O(n^2) algorithms
to O(nlogn) algorithms by divide-and-conquer. My guess is that if FFT
hadn't already been published by the time Knuth's Vol. I came out (without
anything about FFT, of course!), a CS undergraduate would have come up with it
within a semester.
Adam J. Richter
>for that patent to become at all profitable?
A more important question to ask is "would the public have
RSA if there were no software patent incentives." In many cases, there
isn't enough evidence to answer this question, but, for RSA, it appears
that nobody thought to get a patent until the algorithm had been
published for a while, which is why RSA is not restricted by patents
in Europe the way it is in the US. If patent incentives had played
any sort of motivating role for the development of RSA, MIT would
have not have frittered away their international market. It's not
like MIT was a stranger to technology or foreign patent laws.
So, we know that patent incentives were not necessary for the
development of RSA.
--
Adam J. Richter Yggdrasil Computing, Incorporated
(408) 261-6630 "Free Software For The Rest of Us."
Matt Austern
> I suspect that if everybody had easy access to build circuits, and less
> access to developing software, we'd be seeing arguments about how circuit
> patents are evil, terrible, hideous things...
Quite possibly true, and if that were the case then I might be
inclined to believe those arguments. If circuit patents did actually
prevent people from doing things that they could otherwise do easily,
if it appeared that the net impact of circuit patents was harmful
rather than helpful, then I probably would oppose them.
My opposition to software patents has nothing to do with first
principles of philosophy; it's because, in the real world that I live
in, software patents seem to be harmful. This might not be satisfying
if you expect that everything should be a matter of clear-cut
distinctions and philosophical truths, but then, the law isn't about
philosophy: it's about arbitrary distinctions and limits made for
pragmatic real-world reasons. If the world were different, then my
opinions about what the law should be would probably be different too.
--
--matt
keith jack
Matt Austern <ma...@physics.berkeley.edu> wrote:
>In article <3ephd4$a...@newshost.lanl.gov> gre...@lanl.gov (J. S. Greenfield) writes:
>
>> I suspect that if everybody had easy access to build circuits, and less
>> access to developing software, we'd be seeing arguments about how circuit
>> patents are evil, terrible, hideous things...
>
>Quite possibly true, and if that were the case then I might be
>inclined to believe those arguments. If circuit patents did actually
>prevent people from doing things that they could otherwise do easily,
>if it appeared that the net impact of circuit patents was harmful
>rather than helpful, then I probably would oppose them.
Coming from the hardware side, I have to deal with those
nasty patents... :) Sure, it prevents me from taking
the easy way out -- I need to find another way to do the
same thing. It is not easy, and sometimes you need to
just license the patent, if possible.
In the "old days" we did patent searches to avoid the
problem. Today, most people just go ahead, and if you
get caught violating a patent, you cut a deal or
redesign/cancel the chip. Reason is there are just too many
patents to cover...
BTW, if it weren't for patents, last company I worked at wouldn't
have been around long -- instead it's now made substantial
contributions to graphics and multimedia. They were agressive in
protecting their patents, and didn't feel like spending millions on
development to just have somebody copy a new idea.
Companies that don't spend the R&D dollars can sell your
ideas for less than you, killing you in the marketplace... :)
And a company will not spend R&D dollars if it can't get a
return on investment.
So, those choice is cheaper products with little advancement
over time (since no R&D is being done), or slightly more
expensive products that do a lot more...
As a side note, just because something is published does
not mean "it is in the public domain". I've routinely
published things shortly after patent filing...doesn't
mean you can use it... :)
Now the problem of software now being fast enough to replace
some hardware is interesting...
Of course, much of the above is IMHO... :)
--
--------------------------------------------------------------------
Keith Jack kj...@netcom.com Author: Video Demystified
(619) 587-1057 Editor: Digital Video Technology
ftp://ftp.netcom.com/pub/kj/kjack Multimedia Independent Contractor
Henry Baker
Richter) wrote:
> A more important question to ask is "would the public have
> RSA if there were no software patent incentives." In many cases, there
> isn't enough evidence to answer this question, but, for RSA, it appears
> that nobody thought to get a patent until the algorithm had been
> published for a while, which is why RSA is not restricted by patents
> in Europe the way it is in the US. If patent incentives had played
> any sort of motivating role for the development of RSA, MIT would
> have not have frittered away their international market. It's not
> like MIT was a stranger to technology or foreign patent laws.
> So, we know that patent incentives were not necessary for the
> development of RSA.
I attended an MIT Project MAC Christmas party at Ed Fredkin's house in 1973?
(possibly 1974) where a number of people including Fredkin, Moses, etc. were
discussing ways to gain (D)ARPA funding for something as esoteric as number
theory. If I'm not mistaken, I believe that Rivest, Shamir and Adleman were
also there in attendence. I believe that Fredkin suggested hooking the problem
up to something involving national security e.g., encryption or something.
I believe that this germ of an idea eventually resulted in the RSA
algorithm.
I don't recall that the topic of patents ever came up.
James Buster
>In article <MATT.95J...@physics7.berkeley.edu>,
> BTW, if it weren't for patents, last company I worked at wouldn't
> have been around long -- instead it's now made substantial
> contributions to graphics and multimedia. They were agressive in
> protecting their patents, and didn't feel like spending millions on
> development to just have somebody copy a new idea.
Really? What new ideas were those? Can you really justify the "new and
innovative" label you give them? Note that "substantial contributions"
are not necessarily sufficiently interesting to deserve patent protection.
--
James Buster
bit...@netcom.com
Seth Finkelstein
>
>>>> The articles and other material explain this in great detail.
>>>>Having to search - and work around, or license, the tremendous number of
>>>>concepts that go into many programs can be a severe burden.
>>>
>>>And how is this different from any other field in which things are patented?
>
>> In a line, there are big problems in scale and scope.
>I'm unconvinced that your analogy is particularly meaningful. It's fine
>to draw analogies, but when the main issue is--as you say--scale and scope,
>analogies are relatively useless, since these analogies are drawn precisely
>to *exaggerate* the scale and scope of the problem.
The point, however, was to illustrate the lines of the argument.
The case against software patents does not necessarily have to be a case
against all patents. That's the reply to "And how is this different
from any other field in which things are patented?". To be valid, that
line of argument needs the conditions of the fields to be comparable.
The counter-argument is that those conditions are very different.
>And let's remember, the original claim to which I object (and to which I still
>do object) was the claim that algorithm patents flew in the face of the
>*purpose* of the patent system.
What's going on is a shift which is subtle at a philosophical
level. The *purpose* of the patent system is, to go back to the original
source "To promote the progress of science and useful arts, by securing
for limited times to authors and inventors the exclusive right to their
respective writings and discoveries". Note promoting progress is the
goal, and the monopoly property interest is not a natural right, but a
trade-off in service of that goal. The argument often shifts, though, to
an *assumption* that the monopoly is required, making it axiomatic that
this "promotes progress". That is, instead of the goal being progress
and the burden of proof in every case being on the idea that granting
monopoly helps this, the presentation is that monopoly helps progress
and the burden of proof is to show why it doesn't. This is the
sensibility that infuses "why different from other fields", to the
often-seen "Why would a company spend money to develop anything if they
couldn't have a monopoly", shading into "sweat of the brow" type
arguments that investment should grant exclusive rights. The trade-off is
vastly different in software than hardware (remember, scale and scope).
So algorithm patents "fly in the face" of the patent system in that (it
is asserted) they in practice *stifle* progress, not promote it.
>We have yet to see anybody present a credible argument as to how patenting
>algorithms is, at a philosophical level, inimical to the patent system's
>primary purpose of encouraging innovation and the *sharing* of the technical
>knowledge derived from such.
The argument is not so much that any information property
interest is intolerable, but that this one is counter-productive. It's a
sucker argument to turn it to a debate into the philosophy of any
restriction on information, because then it gets dragged into
comparisons with other patents on levels in which the abstraction
distracts from important differences. That's the point of my analogy
In a certain philosophical sense, a housecat is no different from a
tiger, but to argue that they are both just "feline pets" (== monopolies
on information) misses a lot, which matters greatly when you are attacked
by one (== need searches or face infringement suit).
The specifics can go on at length, which is why I just gave a pointer
to a whole collection (ftp to prep.ai.mit.edu, cd /pub/lfp). Should I
just post stuff from there?
>In any case, for those of you who maintain that the patent system is generally
>reasonable, but that algorithm patents are inherently bad, please reconcile
>the following apparent inconsistency:
How about for those of us who maintain that algorithm patents
are inherently bad, but do not have the inclination to argue about the
whole system in general? Surely one can argue that a particular law is
bad without arguing the entirety of the justice system.
> In such a patent system, one can patent a circuit that implements (in
> hardware) an innovative algorithm. However, the same algorithm is
> ineligible for patent protection, if implemented in software.
> Just what justification is there for having such an arbitrary distinction
> between hardware and software implementations?
That it will cost you hundreds of thousands of dollars to
fabricate the circuit in marketable quantities, but only a few thousand
(or zero) to create a program. That you will never give physical copies
to the circuit to whoever wants one, but you can give everyone in the
world a free copy of the program, if you are so inclined. That people
aren't constantly implementing complicated circuits in tinker toys,
gerbil habitats, and plumbing connections, all of which could require
extensive searches and/or payments of royalties to the patent holder.
And so on.
The distinction between hardware and software is as "arbitrary"
as the distinction between body and mind. Yes, there are ways they are
intertwined. But assuming too much is or should be treated as identical
is a great fount of bad philosophy.
>In the course of this discussion, I've come to a tentative hypothesis that
>explains the fairly widespread support for this arbitrary distinction. It's
>quite simple. Lots of people (particularly those on the net) have easy access
^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^
>to computers--either to program themselves, or to use (free or cheap) software
>from others. Consequently, those people tend to feel far more restricted
>by the idea of an algorithm being protected by patent, than by hardware
>patents. Most of them aren't about to go out and build their own hardware.
Exactly. The trade-offs are vastly different in hardware and
software. From your tone, you seem to thinks this is fatally tainted by
self-interest, and that that invalidates the distinction.
>I suspect that if everybody had easy access to build circuits, and less
>access to developing software, we'd be seeing arguments about how circuit
>patents are evil, terrible, hideous things...
ie. "If hardware had similar trade-offs to software, people
would argue that hardware patents were as bad as they say software
patents are". Absolutely. Right. Sure. Is that a refutation?
Haven't you just argued the key point in the above, albeit with
a very negative characterization? Namely, that hardware and software have
significant differences, and these affect whether or not monopolies are
beneficial in the field. That's what we've been saying all along.
Jefferson Ogata
>In article <ogataD2...@netcom.com> og...@netcom.com (Jefferson Ogata) writes:
>
>>It seems to me that the main problem with software patents is the
>>17-year lifespan. 17 years in the development of physical processes
>>is a reasonable time for growth of an industry. But scaled to the
>>high rate of development in the software industry, it is more like
>>of granting) would allow inventors to capitalize on moderate or
>>radical innovation in software design, while not hamstringing the
>>industry.
>
>First of all, I doubt that we can reasonably generalize *all* non-algorithmic
>processes as being suitable for a 17-year life span. We certainly can't do
>so for algorithms. Take the well-known RSA patent. How long did it take
>for that patent to become at all profitable?
>
>takes years just to get a patent. If the true useful life span of a patent
>is only 1.5 years, that lifespan will be over before patent protection is
>granted. During that time, *anybody* will be able to use the algorithm
>royalty-free.
I think you missed the point here. To reiterate: "(e.g. 1.5 years from
the time of granting)". This means: for example, 1.5 years. Actual
time frame could be debated; I was just suggesting shortening the
lifespan of a patent, based on the fact that the software industry
has a higher rate of development than some other industries.
Also I did not state the the truly useful lifespan of a patent is 1.5
years; this is just a suggested time frame that would offer developers
a chance to make some return on algorithm development without hindering
overall development in the industry. Truly useful and unobvious
algorithms would certainly have a much longer useful lifespan, so the
delay in the patent review process would effectively reward innovative
algorithms more, because by the time the patent were granted, the
algorithm would already enjoy widespread use.
>The result would be that inventors would simply maintain new algorithms as
>trade secrets. It would be the only way to protect the value of the
>invention. Now *that* would fly in the face of the purpose of the patent
>system, since the whole point of that system is to encourage the *sharing*
>of knowledge, in order to advance technology...
>
>
>--
>J. S. Greenfield gre...@thelair.zynet.com
>(So what were you expecting?
>A Gorilla?!) "What's the difference between an orange?"
Here again, the shortened lifespan would reduce the impact of patents
on "obvious" innovations. So even though someone might collect license
fees on a relatively obvious algorithm, it would only be for a short
time, so the industry wouldn't suffer as badly while the discoverers
of truly innovative algorithms would still be rewarded.
This suggestion was intended to address the pragmatic issues involved
in software patents, which are very unlikely to be resolved by
modification of the patent review process. True experts in the field
of computer science are not likely to work for the patent office, and
many others would be unable to do so for conflict-of-interest reasons.
You have repeatedly asked "what is the philosophical difference in
software patents?" I don't understand why there must be a philosophical
difference; there are obvious pragmatic differences because of the
nature of software evolution. New software processes are developed at
very high rates, and their modularity means that they get reused
more frequently than in other industries. In fact, good code is
generally designed to be reusable. I believe this warrants treating
software differently, in the interest of helping the software industry
develop; this is in the interest of government and citizenry, as it
benefits them both. The patent is not a strictly philosophical
institution; e.g. it has a 17-year lifespan--what's philosophical about
that?
--
Jefferson Ogata og...@netcom.com
"Animals without backbones hid from each other or fell down. Clamasaurs and
oysterettes appeared as appetizers. Then came the sponges, which sucked up
about ten percent of all life." - Firesign Theatre
Kai Henningsen
> How about the following: in order to get a patent, inventors must prove
> they have maintained a trade secret for 5 years or so, without anyone
> else independently discovering the invention.
I think this is a very bad idea. First, it says a patent *depends+ on
keeping it secret, which is quite the opposite of what's wanted. Second,
in "fast" industries like software, a patent on 5 year old inventions has
no positive value for the community at all - if it's been kept secret
*and* not reinvented, it's bound to be just about useless.
No, anything that works for a fast industry *must* have a fast lifecycle
*from the beginning*.
If it takes years to get software patents, then software patents are
*necessarily* A Bad Thing[tm]. And why should it? If then only have a
short life time, errors in granting them have much less impact, so it
should be possible to speed the process up.
> That way, you wouldn't have so many patents on obvious inventions,
> but you would get the original intended benefit of patents (the
> invention isn't lost forever if the inventor dies, and the inventor
> has incentive to put it into the public domain after recovering
> the initial R+D costs).
No software invention is lost forever when the inventor dies, *if* it has
got use in a product - you can always reverse engineer the product. That's
the difference between manufacturing process patents and others; it
applies to other industries as well.
By the way, just how do patents give an incentive to put something in the
public domain? Just the opposite, it seems. What they *do* encurage is
*publishing and licensing*. For that to be useful, the life cycle has to
be realistic for the target industry.
Kai
--
Internet: k...@ms.maus.de, k...@khms.westfalen.de
Bang: major_backbone!{ms.maus.de!kh,khms.westfalen.de!kai}
## CrossPoint v3.02 ##
Matthew Russotto
>This past year, didn't IBM offer to provide the PTO with a catalog of
>algorithms, to be used for prior art searches by examiners? Companies like
>IBM are *extremely* concerned about patents being granted for algorithms
>that they have been using for years, and the potentially legal problems
>that would arise from such.
IBM may be concerned, but they have a defense-- they patent everything they
can, and use the patents as bargaining chips. The rest of us are left out
in the cold.
Jonathan Eifrig
Henry Baker <hba...@netcom.com> wrote:
>I attended an MIT Project MAC Christmas party at Ed Fredkin's house in 1973?
>(possibly 1974) where a number of people including Fredkin, Moses, etc. were
>discussing ways to gain (D)ARPA funding for something as esoteric as number
>theory. If I'm not mistaken, I believe that Rivest, Shamir and Adleman were
>also there in attendence. I believe that Fredkin suggested hooking the problem
>up to something involving national security e.g., encryption or something.
>
>I believe that this germ of an idea eventually resulted in the RSA
>algorithm.
Now, this touches on the reason that the RSA patent *really*
pisses me off. Rivest, Shamir, and Adleman developed RSA on Government
research grants! Clearly, Rivest, et. al., didn't need their future
commercial rights to their work to motivate their research; DARPA was
paying their salaries!
It seems the height of idiocy to spend public monies to support
software researchers and then let them patent the results of such
research, thereby denying the public the benefits they were expecting.
If we're going to spend public funds on basic research (and I think we
should), then I think the public as a whole should reap the benefits of
it.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
"Knee-jerk liberals and all the certified saints of sanctified
humanism are quick to condemn this great and much-maligned Transylvanian
statesman."
-William F. Buckley, Jr., "The Wit and Wisdom of Vlad the Impaler"
Jack Eifrig (eif...@cs.jhu.edu) The Johns Hopkins University, C.S. Dept.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Doug Edwards
software and algorithms are to be disallowed, how can we
justify continuing to allow patents on hardware which simply
implements particular algorithms?
I have a short answer for this.
Patents on hardware which does nothing but implement
particular algorithms should *never* be allowed. To get
*any* patent on *anything*, the developer should be required
to demonstrate that realization of the idea being patented
as a physical device is essential and that its function
could not possibly be simulated in software, at least not in
any manner which would be of any practical use whatever.
This would allow patents on medications, alternative energy
sources, pollution-free vehicles, and other things naturally
thought to be entitled to patent protection. It would even
allow patents on computer hardware fabrication techniques,
and on fundamental characteristics of computer processors
which would be of no use to simulate in software on a
different processor. But it would disallow, for instance,
patenting *any* application or implementation of the LZW
compression algorithm --- even in, for instance, modem
hardware.
Think this one over.
John Nagle
> A more important question to ask is "would the public have
>RSA if there were no software patent incentives." In many cases, there
>isn't enough evidence to answer this question, but, for RSA, it appears
>that nobody thought to get a patent until the algorithm had been
>published for a while, which is why RSA is not restricted by patents
>in Europe the way it is in the US.
No, the story is that they published before patenting to avoid being
hit with a secrecy order.
John Nagle
John Nagle
>In article <3ephd4$a...@newshost.lanl.gov> gre...@lanl.gov (J. S. Greenfield) writes:
>> I suspect that if everybody had easy access to build circuits, and less
>> access to developing software, we'd be seeing arguments about how circuit
>> patents are evil, terrible, hideous things...
That happened, but it happened back in the 1920s and 1930s, as
radio was getting going. A good discussion for the non-technical reader is
in "Empire of the Air".
John Nagle
Paul Shirley
>
>The industry that stands to benefit the most in the near term from
>software patents is the legal profession. Having to hire lawyers
More worrying, we will see the same patent swapping and hoarding that
goes on in most large manufacturing business. In our case that means
companies like Microsoft,Apple,IBM will use technology effectively for
free that smaller companies will have to pay for.
--
Paul Shirley: SemiProfessional Coffee & Chocolate Taster
Paul Shirley
>Actually, if EFF wanted to do something REALLY contructive, they would
>help work out a method to speed research for patent research. The root
>cause of this debate is that Compuserve inadvertantly released into the
>public domain a file format that required the use of a patented algorithm
>do create.
>
>Fighting an existing patent is a waste of time and money, since they've
>already established a precedent for licencing the technology.
>
So the best way to find patents is to stop them *before* they get the
patent. A good way is to make sure every possible idea however trivial
gets published, archived and indexed (the net seems a reasonable place)
and then thrust forcefully at patent offices round the world as prior art.
If thorough prior art searches had been performed I suspect very few
software patents would exist.
Eric E. Bardes
> I have a short answer for this.
> Patents on hardware which does nothing but implement particular
> algorithms should *never* be allowed. To get *any* patent on
> *anything*, the developer should be required to demonstrate that
> realization of the idea being patented as a physical device is
> essential and that its function could not possibly be simulated in
> software, at least not in any manner which would be of any practical
> use whatever.
A friend of mine once quoted that computer science isn't about computers
any more than astronomy is about telescopes. Anything software can be
implemented in hardware and any hardware can be implemented in software.
With that in mind, it is difficult to draw nice clean lines between
hardware and software. I would hate to establish guidelines based upon
our traditional views that the CPU is hardware and the programs are
software. Patents are all about revolutionary and non traditional ways
of thinking of things. For example: anybody have an accelerated video
card in their system?
Okay, back to Patents. One of the big complaints about the United
States is somebody (usually outside the US) develops, manufactures and
delivers technology in good faith that all the patents have been fully
researched. Only to discover that a "Submarine Patent" has just
surfaced rendering their product in violation of the patent. I know
this has been addressed in the recent GATT treaties.
Enough ranting.
--
Take Care, Eric ,,,
http://www.carsinfo.com/~eric/ (o o)
------------------------------oOOo-(_)-oOOo--------------------------------
What if, there were no hypothetical situations ...
J. S. Greenfield
>>I think a lot of algorithms people--including myself--would disagree with
>>you. Many algorithms are not trivial to develop, as you seem to suggest.
>
>Maybe many are not, but many are. In any case what I was saying was that
>most *software* only uses trivial algorithms.
This much I'll agree with. Most programs will use very few (or no)
nontrivial algorithms. Of course, a particular non-trivial algorithm
may just be central to a program's utility.
>Software engineering *techniques* are of highly academic interest and
>there isn't so much of a sharp boundary between them.
If you mean they're of *only* academic interest, I'll have to disagree.
Many non-academic organizations spend huges sums of money on training,
consulting, and software related to various software engineering
techniques that they want to use.
>But look at
>software packages... a lot more people are known for the excellent
>software packages (incorporating good SE technique) they wrote than
>are known for developing important algorithms.
Commercial software packages ain't known for great algorithms, because
the users don't know from algorithms. Then again, they don't know from
software engineering, either. They know only what works, and works
well.
>And a lot of that
>software incorporates only algorithms that the programmers made up
>on the spot, not looked up in the literature.
The vast majority of which are trivial, as I think we agreed, above.
>>You contradict yourself. First, you say that algorithms that are patented--
>>even the really good ones--could be developed overnight by "lots of smart
>>people," most even by high school students. Then you claim that the patent
>>examiner problem can *never* be solved without making the very *best*
>>computer scientists examiners.
>>
>>Which is it? Are these algorithms so trivial that lots of smart people
>>could invent them overnight, or are the algorithms so complex that only
>>the very best computer scientists could serve as competent examiners?
>>
>>It's inconceivable to me that *both* could be true.
>
>It seems not only conceivable, but obvious to me that both are true.
>Many (or most) algorithms are trivial, but whether this is true for a
>particular algorithm is very hard to decide. Since you say that
>you're an algorithms person, you should know that coming up with a
>good algorithm is often as much a matter of intuition and luck as it
>is skill... unlike many other engineering tasks it can't be easily
>broken down into steps that can be refined until you have the best
>possible outcome. Two equally good computer scientists can look at a
>problem and after a night's work one might say "hmmm... this seems
>hard... I don't think you can do it in better than O(n^2) time" and
>the other looks at it and after fiddeling with ideas for an hour yells
>"Heureka! I can do it in linear time!". But until you've made the
>breakthrough you just don't know! Is it hard? Isn't it?
And you don't think that *either* one could characterize the O(n^2)
algorithm as pretty mundane and the O(n) algorithm as much more interesting?
I'm sorry, but this argument just doesn't cut it for me. Finding great
algorithms is often the result of momentary inspiration, but so what.
Many people can recognize a great idea, even if they couldn't have
developed the idea themselves.
In fact, if there is *any* weakness in an (educated/experienced) person's
ability to judge greatness, it's in *underestimating* the difficulty
of developing the algorithm. Many great ideas are deceptively simple.
That tends lead people to believe that *they* could have come up with the
idea themselves.
Consequently, I would expected (well-trained) examiners to be much more likely
to *underestimate* the significance of a discovery than to *overestimate*
it.
And in any case, I certainly can't agree that one needs to be a genius to
distinguish between the mundane and products of genius.
>So what I'm saying is that a patent examiner might look at a patent
>claim and ask themselves "could I develop this given problem X?" But
>even if they are decent computer scientists, just because they can't
>come up with a solution right then doesn't mean that 100 other people
>(including aforementioned high-school students) couldn't solve the
>problem overnight! Until you've solved the problem yourself you can't
>really know how hard it is. Therefor the patent examiners have to be
>so good that they could, on their own, come up with *all* the
>solutions for which patent claims are filed. (But then we should just
>leave them working in research labs cranking out algorithms to really
>hard problems rather than shuffeling patent claims.)
As I said above, I absolutely disagree. What's more, this is no more
a problem for algorithms than for anything else submitted to the patent
office.
By your argument, the patent system can only work if the best researchers
in *all* fields server as examiners. Experience would see to have
disproved that assertion.
>>In fact, I don't even believe that *either* is true. I believe that mere
>>mortals can be experienced enough to recognize algorithms that they, and most
>>others, would not trivially develop.
>
>And I disagree. There probably are a number of algorithms that any
>reasonably well-trained computer sciencist could look at and say, "wow,
>this is hard... I don't think many people could come up with this." But
>most of the algorithms I've studied do not fall into this category. Until
>you've tried to solve it for a while and failed, it's hard to say "this is
>hard."
But even if that were the case, the problem is not the one of which everyone
is complaining. People aren't complaining that algorithms worthy of patent
protection aren't getting it. They're complaining that trivial algorithms
are being granted patents.
Your argument would seem to concede that better-trained examiners are likely
to alleviate *that* problem.
J. S. Greenfield
>Maybe FFT is pretty obvious after all. Have you ever taken a CS algorithms
>course?
Actually, I never have taken a *course* in algorithms. But then again,
I do have a PhD in CS. So what?
>Nearly the entire course is concerned with converting O(n^2) algorithms
>to O(nlogn) algorithms by divide-and-conquer.
Well, I guess that would depend upon who was teaching the course...
>My guess is that if FFT
>hadn't already been published by the time Knuth's Vol. I came out (without
>anything about FFT, of course!), a CS undergraduate would have come up with it
>within a semester.
You know what, maybe the theory of relativity is pretty obvious after all. I
mean, when Einstein developed it, it *seemed* pretty esoteric, but these days
they teach it to undergraduates! And maybe the Calculus really wasn't all
it was cracked up to be. After all, today high school students can do
calculus...
The phenomenom you describe is known as the growth of technology. It is
precisely why the patent system seeks to have inventions shared with the
public, rather than hidden away as trade secrets. With the sharing of such
knowledge, the technology advances. Eventually, the technology becomes
much more mundane--in that it is well-known and widely understood. That
doesn't lessen the importance of the discovery at the time.
When Hoare first discovered QuickSort in the late 50's, he couldn't express it
to others. It wasn't until Algol--a language that supported recursive
procedures--was defined, that Hoare was able to write down a meaningful
description of the algorithm. QuickSort is, of course, now one of the
first divide-and-conquer algorithms taught to students in *introductory*
CS classes.
So what? Does that mean the discovery was of little significance at the time?
I think you're suffering from what's known as 20/20 hindsight--as in, after
the algorithm (or the knowledge that led to the development of the algorithm)
is shown to you, you think that you could have invented it yourself.
As I stated in another post, I think this is a trait common to most people.
Consequently, well-trained patent examiners for algorithms are more likely to
be too *conservative* in identifying algorithms as significant, than to be
to liberal in doing so--as many folks seem to have been arguing here.
J. S. Greenfield
>>Take the well-known RSA patent. How long did it take
>>for that patent to become at all profitable?
>
> A more important question to ask is "would the public have
>RSA if there were no software patent incentives."
It's not a more important question in this case. I was merely providing
one example of an algorithm that required quite a long time before it
had significant commercial value. Since I was arguing against a
suggestion that algorithm's, in general, don't need long period's of
protection, this was the appropriate question to ask.
>In many cases, there
>isn't enough evidence to answer this question, but, for RSA, it appears
>that nobody thought to get a patent until the algorithm had been
>published for a while, which is why RSA is not restricted by patents
>in Europe the way it is in the US. If patent incentives had played
>any sort of motivating role for the development of RSA, MIT would
>have not have frittered away their international market. It's not
>like MIT was a stranger to technology or foreign patent laws.
>So, we know that patent incentives were not necessary for the
>development of RSA.
Don't associate it with MIT. Associate it with Rivest, Shamir, and
Adleman. I feel quite sure that they didn't ask the corporate counsel's
permission prior to publishing.
In any case, I wouldn't dispute that the RSA algorithm is an example of
an algorithm that probably would have been invented regardless of patent
law.
That said, I don't think we can judge the usefulness of the patent system on
such anecdotal instances. I don't think it allows you to reach any general
conclusions about the effect of the system.
J. S. Greenfield
>My opposition to software patents has nothing to do with first
>principles of philosophy; it's because, in the real world that I live
>in, software patents seem to be harmful.
How can you reach an empirical conclusion as to whether or not the
patent system can function for algorithms, when the only experience we
have is with a patent system consisting of inadequately-trained
examiners, and a non-existent catalog of prior art?
J. S. Greenfield
> As a side note, just because something is published does
> not mean "it is in the public domain". I've routinely
> published things shortly after patent filing...doesn't
> mean you can use it... :)
Of course, you have no protection between the time you file and the time
the patent is granted. *Anybody* can use your invention during that
period, royalty-free...
Jim Freeman
Keith Stone <kst...@crewstone.com> wrote:
>In article <3eknhi$3...@infonaut.com>, jf...@infonaut.com (Jim Freeman) wrote:
>>
>> No need to fight the patent - just make it irrelevant, work around it
>> without infringing - innovate instead of litigate.
>
>Agreed. If developers feel the LZW license is more trouble than it's
>worth, an alternative will result. If folks find that the cost of LZW is
>less than the hassle of creating an alternative, that's fine too. In
>either case, the issue is resolved without boycotts, mail-bombing, and
>lawsuits.
For compression, an alternative already exists with gzip. The cost from
this point is supplanting LZW in GIF with an available alternative.
Done the right way, this cost could be minimal.
>My real concern is that patent research is a pain in the butt, and more of
>these flaps are going to crop up. Since patents are a way of life, it
>seems more productive (to me at least) to solve the issue up front than to
>wait for an eruption and get out a fleet of lawyers.
I can't bring myself to agree that patents are a way of life - I certainly
don't want them to be the way of MY life. My perception is that the issues
to be solved up front with the patent process are non-trivial and long-term.
In the meanwhile the problems/issues serve (and will continue to do so) as
barriers to "progress in the useful arts and sciences", contrary to the
intent of the law.
...jfree
--
Jim Freeman
jf...@caldera.com
J. S. Greenfield
>I attended an MIT Project MAC Christmas party at Ed Fredkin's house in 1973?
>(possibly 1974) where a number of people including Fredkin, Moses, etc. were
>discussing ways to gain (D)ARPA funding for something as esoteric as number
>theory. If I'm not mistaken, I believe that Rivest, Shamir and Adleman were
>also there in attendence.
Perhaps Rivest and Shamir were. I don't know when they came to MIT. Len
Adleman, on the other hand, would have still been a grad student at Berkeley,
so it seems unlikely that he was there...
>I believe that Fredkin suggested hooking the problem
>up to something involving national security e.g., encryption or something.
>
>I believe that this germ of an idea eventually resulted in the RSA
>algorithm.
More likely it was just an interesting coincidence. According to Adleman's
account of the chronology (described in a NYT bio a few months back), he
arrived at MIT just after Diffie and Hellman's classic paper "New directions
in cryptography" was published (1976). By luck, Adleman was assigned an
office next to Ron Rivest's. Ron Rivest was enamored of Diffie's concept
for public-key cryptography, and vowed that he would develop the first
example of a public-key cryptosystem. Adleman's account certainly makes
it sound as though the Diffie-Hellman paper was the primary inspiration for
the development of RSA.
>I don't recall that the topic of patents ever came up.
I don't doubt that patents weren't an issue of concern to them. Adleman,
who had the role of trying to break cryptosystems developed by Rivest and
Shamir, initially didn't feel his name should go on the paper. He then
agreed to have it put on--in the last position--since he figured he'd need
as many papers as he could get when he went up for tenure. According to
the NYT article, he felt it was the least important paper his name would
ever go on, at the time. It wasn't until after he saw the response to the
paper that he realized the significance of the cryptosystem.
So, viewed in a vacuum, there's little doubt that patent protection did not
play a direct role in encouraging the development of RSA. Of course, as I
said before, we can't judge the whole patent system on such an anecdotal
example. In fact, we can't even fully evaluate the role that patent
played on RSA *indirectly*, because RSA was *not* developed in a vacuum.
How are we to judge whether knowledge gained from prior inventions--which
may, themselves, have been affected by the patent system--played a role in
the eventual development of any given algorithm?
J. S. Greenfield
> What's going on is a shift which is subtle at a philosophical
>level. The *purpose* of the patent system is, to go back to the original
>source "To promote the progress of science and useful arts, by securing
>for limited times to authors and inventors the exclusive right to their
>respective writings and discoveries". Note promoting progress is the
>goal, and the monopoly property interest is not a natural right, but a
>trade-off in service of that goal. The argument often shifts, though, to
>an *assumption* that the monopoly is required, making it axiomatic that
>this "promotes progress". That is, instead of the goal being progress
>and the burden of proof in every case being on the idea that granting
>monopoly helps this, the presentation is that monopoly helps progress
>and the burden of proof is to show why it doesn't. This is the
>sensibility that infuses "why different from other fields", to the
>often-seen "Why would a company spend money to develop anything if they
>couldn't have a monopoly", shading into "sweat of the brow" type
>arguments that investment should grant exclusive rights.
Whne you live in a system in which patent protection for inventions is well-
established, I believe that the burden of proof is *properly* placed upon
those who claim that technology of type X is somehow different from all
other technologies, and therefore unsuitable for protection via the patent
system.
>The trade-off is
>vastly different in software than hardware (remember, scale and scope).
>So algorithm patents "fly in the face" of the patent system in that (it
>is asserted) they in practice *stifle* progress, not promote it.
How can you reach an *empirical* conclusion about the efficacy of the
patent system for algorithms when the *only* practical experience we have
is with a system that is admittedly--by all involved, including the PTO--
currently ill-prepared to properly handle algorithm patents?
I cannot accept such conclusions which suggest that the patent system
is unworkable, and incapable of providing the desired benefit to society,
on the basis that the PTO is *currently* incompetent in handling such matters.
>>We have yet to see anybody present a credible argument as to how patenting
>>algorithms is, at a philosophical level, inimical to the patent system's
>>primary purpose of encouraging innovation and the *sharing* of the technical
>>knowledge derived from such.
>
> The argument is not so much that any information property
>interest is intolerable, but that this one is counter-productive.
You are assuming facts not in evidence. I hope you're a theoretician and not
an empirical scientist. :) (That's in jest. Please don't take offense.)
>It's a
>sucker argument to turn it to a debate into the philosophy of any
>restriction on information, because then it gets dragged into
>comparisons with other patents on levels in which the abstraction
>distracts from important differences.
But you are ignoring an important difference, also--namely, the fact that
the patent system functions for other technologies because it has been
doing so for a long time, and is, consequently, well-prepared to do so.
At this point in time, we have no evidence to suggest that the system cannot
work equally well once it makes appropriate adjustments to handle this
technology.
>>I suspect that if everybody had easy access to build circuits, and less
>>access to developing software, we'd be seeing arguments about how circuit
>>patents are evil, terrible, hideous things...
>
> ie. "If hardware had similar trade-offs to software, people
>would argue that hardware patents were as bad as they say software
>patents are". Absolutely. Right. Sure. Is that a refutation?
No, my comment is a characterization of how people react to feeling some
restriction on *themselves*. In other words, many people react to this issue
primarily because it hits home for them, not because of rational analysis
of the potential costs and benefits of patents for algorithms. I'd expect
the various majority of these folks to sing a very different tune were *they*
to invent the next great algorithm...
> Haven't you just argued the key point in the above, albeit with
>a very negative characterization? Namely, that hardware and software have
>significant differences, and these affect whether or not monopolies are
>beneficial in the field. That's what we've been saying all along.
I concede that there are differences. But you will have to concede that we
do not have the practical experience--with a patent system that is *prepared*
to handle the technology--to conclude that patents are inherently inimical,
rather than beneficial, to the field.
J. S. Greenfield
>>In any case, a 1.5 year lifespan is most assuredly useless. For one thing, it
>>takes years just to get a patent. If the true useful life span of a patent
>>is only 1.5 years, that lifespan will be over before patent protection is
>>granted. During that time, *anybody* will be able to use the algorithm
>>royalty-free.
>
>I think you missed the point here. To reiterate: "(e.g. 1.5 years from
>the time of granting)". This means: for example, 1.5 years.
I didn't miss the point. It wasn't my argument that the patent-holder
would not receive 1.5 years of protection. It's just my argument that such
a short period would hold little benefit for the patent-holder.
>Actual
>time frame could be debated; I was just suggesting shortening the
>lifespan of a patent, based on the fact that the software industry
>has a higher rate of development than some other industries.
I'm not necessarily opposed to a shorter lifespan. However, I think that
*any* lifespan that is reasonable in terms of serving the intended purpose
of the patent system (that is, giving the creator sufficient benefit to
encourage the creator to share the invention with others) will probably
be too long as far as those opposed to algorithm patents are concerned.
>Also I did not state the the truly useful lifespan of a patent is 1.5
>years; this is just a suggested time frame that would offer developers
>a chance to make some return on algorithm development without hindering
>overall development in the industry. Truly useful and unobvious
>algorithms would certainly have a much longer useful lifespan, so the
>delay in the patent review process would effectively reward innovative
>algorithms more, because by the time the patent were granted, the
>algorithm would already enjoy widespread use.
If the true useful life span is considerably longer, then the creator will
probably be better-served by maintaining the algorithm as a trade secret,
and milking it for it's entire useful life span. That was my point.
>>The result would be that inventors would simply maintain new algorithms as
>>trade secrets. It would be the only way to protect the value of the
>>invention. Now *that* would fly in the face of the purpose of the patent
>>system, since the whole point of that system is to encourage the *sharing*
>>of knowledge, in order to advance technology...
>
>Here again, the shortened lifespan would reduce the impact of patents
>on "obvious" innovations. So even though someone might collect license
>fees on a relatively obvious algorithm, it would only be for a short
>time, so the industry wouldn't suffer as badly while the discoverers
>of truly innovative algorithms would still be rewarded.
How about we take a more direct approach--like trying to create a patent
system that is properly prepared to weed out the "obvious" innovations.
That's most of what I've been saying all along--let's establish a patent
system with well-trained examiners and a good catalog of prior art, and
*then* lets evaluate whether or not the system works.
>This suggestion was intended to address the pragmatic issues involved
>in software patents, which are very unlikely to be resolved by
>modification of the patent review process. True experts in the field
>of computer science are not likely to work for the patent office, and
>many others would be unable to do so for conflict-of-interest reasons.
Several people have been bringing this up, but we have yet to see any
credible exmplanation as to why the system can only work with geniuses.
Our practical experience with the rest of the patent system is that it works
reasonably well without such geniuses as examiners. My strong intuition--
based upon my practical experience in life--is that evaluation of algorithms
won't be significantly different.
Just why do you think that the very best computer scientists would have to
be examiners for the system to work?
J. S. Greenfield
> Now, this touches on the reason that the RSA patent *really*
>pisses me off. Rivest, Shamir, and Adleman developed RSA on Government
>research grants! Clearly, Rivest, et. al., didn't need their future
>commercial rights to their work to motivate their research; DARPA was
>paying their salaries!
>
> It seems the height of idiocy to spend public monies to support
>software researchers and then let them patent the results of such
>research, thereby denying the public the benefits they were expecting.
>If we're going to spend public funds on basic research (and I think we
>should), then I think the public as a whole should reap the benefits of
>it.
Well, you may not be satisfied, but the public as a whole *does* benefit
(and more than just from new technology). The government gets an automatic,
royalty-free license to use all patented inventions that are developed with
governmental (or with partially-governmental) funding.
So, just as the public contributes, as a whole, to the development of the
invention, the public benefits, as a whole, from the inventions created.
Now I'm sure many people would like to benefit *individually* from those
creations. Whether or not that would be beneficial to society, on the
whole, is debateable--and I certainly don't claim to have the answer.
Henry Baker
Greenfield) wrote:
> In article <hbaker-0801...@192.0.2.1> hba...@netcom.com (Henry
Baker) writes:
>
> >Maybe FFT is pretty obvious after all. Have you ever taken a CS algorithms
> >course?
> >Nearly the entire course is concerned with converting O(n^2) algorithms
> >to O(nlogn) algorithms by divide-and-conquer.
>
> Well, I guess that would depend upon who was teaching the course...
>
> >My guess is that if FFT
> >hadn't already been published by the time Knuth's Vol. I came out (without
> >anything about FFT, of course!), a CS undergraduate would have come up
with it
> >within a semester.
Knuth Vol. I came out in 1968, mind you, only 3 years after Cooley-Tukey.
> You know what, maybe the theory of relativity is pretty obvious after all. I
> mean, when Einstein developed it, it *seemed* pretty esoteric, but these days
> they teach it to undergraduates! And maybe the Calculus really wasn't all
> it was cracked up to be. After all, today high school students can do
> calculus...
Well, as you probably already know, Einstein wasn't the first to come up
with the equations of Special Relativity. That was already done by Fitzgerald
and others. The equations worked, but it was Einstein who was able to explain
_why_ they worked. (We're still waiting for an 'Einstein' to explain why
Quantum Mechanics works; we know the equations, and they produce the right
answers, but they make no sense!) Note, however, that Einstein would probably
_not_ have had priority on the equations for patent purposes.
> When Hoare first discovered QuickSort in the late 50's, he couldn't express it
> to others. It wasn't until Algol--a language that supported recursive
> procedures--was defined, that Hoare was able to write down a meaningful
> description of the algorithm. QuickSort is, of course, now one of the
> first divide-and-conquer algorithms taught to students in *introductory*
> CS classes.
>
> So what? Does that mean the discovery was of little significance at the time?
>
> I think you're suffering from what's known as 20/20 hindsight--as in, after
> the algorithm (or the knowledge that led to the development of the algorithm)
> is shown to you, you think that you could have invented it yourself.
Not at all. A number of people _did_ independently come up with FFT,
some several years before Cooley & Tukey made it famous in 1965.
According to Blahut, "It was not generally realized until a few years later
[than Cooley-Tukey 1965 paper] that there was an earlier FFT algorithm, quite
different from the Cooley-Tukey FFT, due to Good (1960) and Thomas (1963).
The Good-Thomas algorithm had failed to attract much attention at the time
it was published." Blahut, R.E. Fast Algorithms for Digital Signal
Processing. Addison-Wesley, 1985.
References:
Cooley, J.W. and Tukey, J.W. "An Algorithm for the Machine Computation
of Complex Fourier Series". Math. Comp. 19 (1965), 297-301.
Good, I.J. "The Interaction Algorithm and Practical Fourier Analysis".
J. Royal Statist. Soc., Ser. B 20 (1958), 361-375; addendum, 22 (1960),
372-375.
Thomas, L.H. Using a Computer to Solve Problems in Physics. in
Applications of Digital Computers, Ginn & Co., Boston, MA, 1963.
Butler, J., and Lowe, R. "Beam-forming Matrix Simplifies Design of
Electronically Scanned Antennas". Electronic Design 9 (1961),
170-173. Essentially Cooley-Tukey.
Levinson, N. "The Weiner RMS Error Criteria in Filter Design and
Prediction". J. Math. Phys. 25 (1947), 261-278. (So fast algorithms
are as old as I am!!)
Henry Baker
Greenfield) wrote:
> In any case, I wouldn't dispute that the RSA algorithm is an example of
> an algorithm that probably would have been invented regardless of patent
> law.
I've heard rumors that there was some grousing at NSA when the RSA algorithm
was published, and even more when it was patented. The rumor is that
people at the NSA invented the RSA algorithm in the 1960's, but couldn't
publish it because of national security (or perhaps there wasn't enough
room in the margin of their copy of Hardy&Wright :-). Due to the secrecy,
something like this apparently couldn't be considered as prior art.
Paul Shirley
>In fact, I don't even believe that *either* is true. I believe that mere
>mortals can be experienced enough to recognize algorithms that they, and most
>others, would not trivially develop. I believe that it is unfair to judge
>the performance of "mortal" examiners who are appropriately *trained*, on
>the basis of the performance of examiners who are *not* trained in the
>field of computer science.
>
>(Remember, it was not until last year that the PTO decided to, experimentally,
>hire some examiners whose backgrounds were in computer science. They still
>have not made computer science a field which qualifies for the patent bar.)
>
Its perfectly fair to judge a system that does not hire appropriately
qualified people to do its work.
J. S. Greenfield
>I've heard rumors that there was some grousing at NSA when the RSA algorithm
>was published, and even more when it was patented. The rumor is that
>people at the NSA invented the RSA algorithm in the 1960's, but couldn't
>publish it because of national security (or perhaps there wasn't enough
>room in the margin of their copy of Hardy&Wright :-). Due to the secrecy,
>something like this apparently couldn't be considered as prior art.
By my understanding, prior art includes *only* that which is disseminated
to the public. If the NSA discovered the cryptosystem and kept it secret,
it's the logical equivalent of a trade secret--something that doesn't
constitute prior art.
Of course, if NSA did come up with the RSA cryptosystem, they would have
had to have developed the idea of public-key cryptography beforehand. Have
you heard any rumors of grousing about Diffie and Hellman's classic paper
on such, or on the Diffie-Hellman key-exchange algorithm?
Jefferson Ogata
>In article <ogataD2...@netcom.com> og...@netcom.com (Jefferson Ogata) writes:
>>Also I did not state the the truly useful lifespan of a patent is 1.5
>>years; this is just a suggested time frame that would offer developers
>>a chance to make some return on algorithm development without hindering
>>overall development in the industry. Truly useful and unobvious
>>algorithms would certainly have a much longer useful lifespan, so the
>>delay in the patent review process would effectively reward innovative
>>algorithms more, because by the time the patent were granted, the
>>algorithm would already enjoy widespread use.
>
>If the true useful life span is considerably longer, then the creator will
>probably be better-served by maintaining the algorithm as a trade secret,
>and milking it for it's entire useful life span. That was my point.
I disagree with you on this point. It seems to me that if an
algorithm discoverer (not creator, in my philosophy--the algorithm
always existed) keeps it a trade secret, they run the risk of
someone else patenting the algorithm. In that case they might end up
paying license fees on an algorithm they could have been collecting
fees on, since their trade secret will not qualify as prior art (in
my understanding). Thus there is a competitive pressure to patent
the algorithm first. Since many people are working from the same
published information, there is always a fair level of risk that
your innovation will be independently discovered by someone else.
>>>The result would be that inventors would simply maintain new algorithms as
>>>trade secrets. It would be the only way to protect the value of the
>>>invention. Now *that* would fly in the face of the purpose of the patent
>>>system, since the whole point of that system is to encourage the *sharing*
>>>of knowledge, in order to advance technology...
>>
>>Here again, the shortened lifespan would reduce the impact of patents
>>on "obvious" innovations. So even though someone might collect license
>>fees on a relatively obvious algorithm, it would only be for a short
>>time, so the industry wouldn't suffer as badly while the discoverers
>>of truly innovative algorithms would still be rewarded.
>
>How about we take a more direct approach--like trying to create a patent
>system that is properly prepared to weed out the "obvious" innovations.
>That's most of what I've been saying all along--let's establish a patent
>system with well-trained examiners and a good catalog of prior art, and
>*then* lets evaluate whether or not the system works.
I think this would be an excellent solution to the problem,
particularly if it were combined with a lifespan appropriate to the
software industry. I'm just very pessimistic about the likelihood it
would happen.
>>This suggestion was intended to address the pragmatic issues involved
>>in software patents, which are very unlikely to be resolved by
>>modification of the patent review process. True experts in the field
>>of computer science are not likely to work for the patent office, and
>>many others would be unable to do so for conflict-of-interest reasons.
>
>Several people have been bringing this up, but we have yet to see any
>credible exmplanation as to why the system can only work with geniuses.
>Our practical experience with the rest of the patent system is that it works
>reasonably well without such geniuses as examiners. My strong intuition--
>based upon my practical experience in life--is that evaluation of algorithms
>won't be significantly different.
>
>Just why do you think that the very best computer scientists would have to
>be examiners for the system to work?
I think there have been so many posts in this thread that it's
getting kind of confused. I didn't say we need the very best
computer scientists; I just said that true experts and others
probably wouldn't be working for the patent office or might have
conflicts of interest. I certainly didn't say we need geniuses.
But consider this: it does take a fair amount of training to even
understand how the FFT (for example) works. In general, truly
innovative algorithms that represent a significant work investment
will be fairly complex. The abstractness of algorithms and the
existence of dual equivalents make many of them difficult to
understand and compare. For example, suppose someone patented an
algorithm for finding the convex hull of a set of points. If I
converted the algorithm to its dual (calculation of a voronoi
region) would I be infringing the patent? The algorithms are
equivalent. This consideration is made more vivid by the
proposition made earlier that we use an algorithm equivalent but
unequal to LZW to resolve the GIF conflict.
ahti heinla
>
>>Maybe FFT is pretty obvious after all. Have you ever taken a CS algorithms
>course?
never, and i've never studied cs anywhere except a few lessons in
high school (big whoop!) but fft is still pretty obvious, the main problem
is perhaps that it seems to be a paradox that this can in fact be done
faster that n^2... if you _know_ that it can be done, then finding the
correct way to do it shouldn't be _very_ hard.
the base idea behind fft was discovered in 20s (1924?); when these
two people (forgot the names; you know who i'm talking about)
reinvented it in 1967 (or was it 66), they called up someone who was
using the base idea back in 20s, and he admitted that his technique was
very similar to the reinvented one...
>My guess is that if FFT
>hadn't already been published by the time Knuth's Vol. I came out (without
>anything about FFT, of course!), a CS undergraduate would have come up with it
>within a semester.
based on knuth vol i only? :) i doubt that... :) but ymmv, let's
not argue over nothing.
ahti
--
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Launchpad is an experimental internet BBS. The views of its users do not
necessarily represent those of UNC-Chapel Hill, OIT, or the SysOps.
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
ssatchell on BIX
Did NSA invent the RSA scheme before or after the government set up a way
to escrow a patent of a Secret or Top Secret process? (It's alledged that
SkipJack is "covered" such that if the details ever leak out it will be
patented.)
Henry Baker
Greenfield) wrote:
> In article <hbaker-0901...@192.0.2.1> hba...@netcom.com (Henry
Baker) writes:
>
> >I've heard rumors that there was some grousing at NSA when the RSA algorithm
> >was published, and even more when it was patented. The rumor is that
> >people at the NSA invented the RSA algorithm in the 1960's, but couldn't
> >publish it because of national security (or perhaps there wasn't enough
> >room in the margin of their copy of Hardy&Wright :-). Due to the secrecy,
> >something like this apparently couldn't be considered as prior art.
>
> By my understanding, prior art includes *only* that which is disseminated
> to the public. If the NSA discovered the cryptosystem and kept it secret,
> it's the logical equivalent of a trade secret--something that doesn't
> constitute prior art.
>
> Of course, if NSA did come up with the RSA cryptosystem, they would have
> had to have developed the idea of public-key cryptography beforehand. Have
> you heard any rumors of grousing about Diffie and Hellman's classic paper
> on such, or on the Diffie-Hellman key-exchange algorithm?
If I remember the rumor correctly, I think that there may have been other
reasons for using an RSA-type encoding than 'public' keys. Even for non-public
keys it would be nice to have some keys more private than others.
J. S. Greenfield
>>If the true useful life span is considerably longer, then the creator will
>>probably be better-served by maintaining the algorithm as a trade secret,
>>and milking it for it's entire useful life span. That was my point.
>
>I disagree with you on this point. It seems to me that if an
>algorithm discoverer (not creator, in my philosophy--the algorithm
>always existed) keeps it a trade secret, they run the risk of
>someone else patenting the algorithm. In that case they might end up
>paying license fees on an algorithm they could have been collecting
>fees on, since their trade secret will not qualify as prior art (in
>my understanding). Thus there is a competitive pressure to patent
>the algorithm first. Since many people are working from the same
>published information, there is always a fair level of risk that
>your innovation will be independently discovered by someone else.
(As a side note, I'm not going to argue over the semantics of creation
versus discovery. I have used both terms in this discussion. I'll
agree that algorithms are discovered, but then again, so are *all*
technical "creations." The terms "creator" and "inventor" seems more natural
to me when talking about patents.)
If the true useful life span is considerably longer than the patent life
span, I expect many creators will take their chances. After all, if the
life span is short, they may not see much of a threat from having to
pay license fees (for a short while) if someone else comes along later,
and patents the invention. What's more, if they're maintain the algorithm
as a trade secret, they will likely not worry about a subsequent discoverer
even *knowing* that they are using the same algorithm.
>>How about we take a more direct approach--like trying to create a patent
>>system that is properly prepared to weed out the "obvious" innovations.
>>That's most of what I've been saying all along--let's establish a patent
>>system with well-trained examiners and a good catalog of prior art, and
>>*then* lets evaluate whether or not the system works.
>
>I think this would be an excellent solution to the problem,
>particularly if it were combined with a lifespan appropriate to the
>software industry. I'm just very pessimistic about the likelihood it
>would happen.
I wouldn't be so pessimistic. The patent office started hiring
computer scientists as examiners (on an experimental basis) last year.
That's the first step. There are many companies and organizations that
are interested in compiling a comprehensive catalog of prior art. I expect
that such a catalog will come to exist in the not-so-distant future.
The process won't be as fast as we all might like, and we'll be dogged
for some time by some of the pre-existing patents, but I expect changes
for the better are likely to occur.
>>Just why do you think that the very best computer scientists would have to
>>be examiners for the system to work?
>
>I think there have been so many posts in this thread that it's
>getting kind of confused. I didn't say we need the very best
>computer scientists; I just said that true experts and others
>probably wouldn't be working for the patent office or might have
>conflicts of interest. I certainly didn't say we need geniuses.
My apologies for misrepresenting your statement.
In any case, I think we have as good a chance of getting expert examiners
in the field of computer science as we do in any other field handled
by the patent office.
>But consider this: it does take a fair amount of training to even
>understand how the FFT (for example) works. In general, truly
>innovative algorithms that represent a significant work investment
>will be fairly complex. The abstractness of algorithms and the
>existence of dual equivalents make many of them difficult to
>understand and compare. For example, suppose someone patented an
>algorithm for finding the convex hull of a set of points. If I
>converted the algorithm to its dual (calculation of a voronoi
>region) would I be infringing the patent? The algorithms are
>equivalent.
My understanding of patent law is that an algorithm cannot be patented
(i.e., *should* not be granted a patent) unless it is applied to a
particular application or class of applications. Consequently, one should
not be able to patent a convex hull algorithm, alone. One could,
potentially, patent a convex hull algorithm for use in, say, constructing
CT images.
It should not infringe the patent to use the same convex hull algorithm
for an application not covered by the patent. If an equivalent algorithm
for calculating a voronai region is used for an application not covered
by the patent (i.e., a novel application), I would not expect it to be an
infringing use.
>This consideration is made more vivid by the
>proposition made earlier that we use an algorithm equivalent but
>unequal to LZW to resolve the GIF conflict.
Well, I don't know what "equivalent but unequal" means.
Joe Buck
In article <hbaker-0801...@192.0.2.1> hba...@netcom.com (Henry Baker) writes:
>Maybe FFT is pretty obvious after all. Have you ever taken a CS algorithms
>course?
The first known discovery of the FFT algorithm was in 1807, by Gauss, who
was attempting to calculate planetary orbits. Gauss was famous for
pulling 30-year-old unpublished notes from his desk every time some
other mathematician discovered something, showing he'd found it long,
long ago. I doubt if Gauss took a CS algorithms course.
Needless to say, the 17 years has probably expired on this one.
--
-- Joe Buck <jb...@synopsys.com> (not speaking for Synopsys, Inc)
Phone: +1 415 694 1729
Jurgen Botz
ssatchell on BIX <ssat...@BIX.com> wrote:
>Did NSA invent the RSA scheme before or after the government set up a way
>to escrow a patent of a Secret or Top Secret process? (It's alledged that
>SkipJack is "covered" such that if the details ever leak out it will be
>patented.)
This has gotta be BS. If it were true then the patent system would
indeed have become a joke.
Michael I Bushnell
>It is the case, however, that it is not generally
>possible, given two algorithms, to tell whether they even solve the
>same problem or not, let alone whether they do it in the same way.
>(It's a simple conclusion from Turing's work.)
>
>A good example of this is the link between the discrete cosine
>transform and the FFT, which look quite different on the surface, but
>really do the same thing underneath.
My goodness! How did you ever reach this conclusion, if it's not
generally possible to do such things?
In some particular cases, it is possible to determine whether two
algorithms do the same thing. In this case, it is possible to
construct a proof that a discrete cosine transform amounts to solving
a particular special case of a Fourier transform.
But given two computer programs, you cannot tell whether they do the
same thing by any automated process. Sometimes, two programs do the
same thing, but there exists no proof of that fact.
This is a trivial application of Turing's Halting Theorem. I thought
you were an "expert". Are you unaware of this theorem?
--
Michael I. Bushnell |
+1 617 253 8568 -+-
m...@gnu.ai.mit.edu |
|
Dave Hamaker
>You know what, maybe the theory of relativity is pretty obvious after all. I
>mean, when Einstein developed it, it *seemed* pretty esoteric, but these days
>they teach it to undergraduates! And maybe the Calculus really wasn't all
>it was cracked up to be. After all, today high school students can do
>calculus...
>When Hoare first discovered QuickSort in the late 50's, he couldn't express it
>to others. It wasn't until Algol--a language that supported recursive
>procedures--was defined, that Hoare was able to write down a meaningful
>description of the algorithm. QuickSort is, of course, now one of the
>first divide-and-conquer algorithms taught to students in *introductory*
>CS classes.
I find it interesting he gravitates to these examples in discussing patent
issues. It is my understanding that Einstein's theories and the Calculus
are NOT patentable material. And, I must say I feel more comfortable with
the idea of QuickSort being like them than being like the apparatus patents
used to focus on. Shucks, he even describes Hoare's result as a "discovery"
when he could have used the "invention" word.
-Dave
d...@cfcl.com
Dave Hamaker
A comment: Isn't it OUR government in this country. In guaranteeing only
the governmental organization itself royalty-free licensing, it makes ME
think of an employee patenting an invention for himself which he developed
on company time.
-Dave
d...@cfcl.com
J. S. Greenfield
> >It is the case, however, that it is not generally
> >possible, given two algorithms, to tell whether they even solve the
> >same problem or not, let alone whether they do it in the same way.
> >(It's a simple conclusion from Turing's work.)
> >
> >A good example of this is the link between the discrete cosine
> >transform and the FFT, which look quite different on the surface, but
> >really do the same thing underneath.
>
> My goodness! How did you ever reach this conclusion, if it's not
> generally possible to do such things?
>
>In some particular cases, it is possible to determine whether two
^^^^
>algorithms do the same thing. In this case, it is possible to
>construct a proof that a discrete cosine transform amounts to solving
>a particular special case of a Fourier transform.
How about in *many* cases? Perhaps even *most* cases that are likely
to arise?
>But given two computer programs, you cannot tell whether they do the
>same thing by any automated process. Sometimes, two programs do the
>same thing, but there exists no proof of that fact.
>
>This is a trivial application of Turing's Halting Theorem. I thought
>you were an "expert". Are you unaware of this theorem?
Perhaps you didn't bother to read my post past the point that you excerpted
above. The whole point of that post was to demonstrate that theoretical
results are of little interest when it comes to predicting what is likely
to happen in practice.
The halting theorem tells us that no machine can, for all programs and all
input, tell us whether a given program halts. Practice tells us that
a computer scientist can determine whether or not virtually any given
program halts.
The theoretical result tells us nothing that is helpful regarding practice.
Likewise--as I said in my last post--in practice, computer scientists are
capable of comparing, conmtrasting, classifying, and cataloging virtually
all algorithms that come up.
Why do you persist in citing theoretical results in support of an argument
about what humans beings can do in practice?
What's more, why do you think the situation is any different from other
technologies? Do you think that it's possible, in theory, to build a
machine that can compare any two given physical process, and determine whether
or not they are equaivalent?
I seriously doubt it...
Richard Matthias
I may have missed the 0 of this discussion, but why is everyone getting
so excited about this LZW patent thing anyway?
Nobody is going to stop *ME* using GIF files. Note the emphasis. There may be
some "principle of the thing" sentiment about this discussion, but for
practical purposes does it really matter if Unisys enforces its patent on LZW
encoding?
Presumably if Unisys gets its way it could stop (or make pay), producers of
commercial graphics software like Microsoft, Corel and Adobe, from using the
GIF format. I don't think it is likely to stop the likes of PICLAB, FRACTINT,
GWS and POVRAY from using it extensively, simply because these programs are
distributed for free. And even if they could stop it from being used in any
future product, there and millions of copies floating around already and
nobody could stop them being passed around even if it was made a capital crime
tomorow.
Phil Zimmerman acknowledges that his PGP software infringes the RSA patent(s),
but he hasn't had his ass kicked yet (he almost did, but thats not the point).
Even if the patent was enforceable it wouldn't take more than a week, and
probably less than that, for someone to come up with a new format and as soon
as it is adopted by one large software supplier, everyone else will use it and
that will be the end of the matter. When a patent was enforced on Phil Katz
to prevent him from developing any further his PKARC archiving software, it
took him a month (as I recall) to write PKZIP and within a year the PKARC
format was dead, nobody uses anything other than PKZIP now.
When you take huge R&D departments (as in the drug company analogy) out of the
loop and replace them with individual genius programers and a virtually instant
software distribution system, patents cease to be a major issue.
Now `look and fell' lawsuits, that's a different story.....
Richard Matthias
Matthew Russotto
>It does not make sense to draw general conclusions about how the patent
>system *must* function for algorithms, on the basis of practical
>experience with a patent office that is not currently prepared to handle
>algorithms.
Algorithm patents put a 20-year (approx) ball and chain on the
software industry. For the 17 years the patent runs, only medium to large
size developers can use it, because the very small ones can't afford the
administrative fees associated with the royalties-- even if the royalties
themselves are very small. If there are enough algorithm patents, very small
developers are put completely out of business, and medium sized ones operate
at a severe disadvantage-- the small ones because they can't afford the patent
searches, and the medium sized ones because they don't have enough "chips" of
their own to use the patents for free.
Worse, there's the "submarine patent" problem-- an algorithm can be
independently reinvented and in wide use before a patent on it is granted.
When that patent is granted, the re-inventor is stuck, denied the right to his
own invention. IMO this happens far more often in the fast-moving software
industry than in other industries. It could be solved, but only by having the
patent office take a much shorter time to grant patents. And that they
aren't going to do.
And, of course, there's the ridiculous claims which are essentially unbeatable
because the patent holders have better lawyers than the challengers-- RSAs
claims to all public key encryption, for example. The RLE patents. Someone
mentioned a patent on the use of a one-bit field to determine whether the next
code was uncompressed data or compressed data. The infamous XOR cursor patent.
there's many patents on ideas (yes, ideas, IMO) which are either trivial,
in wide use before their supposed "invention", or both. But given the
presumption that the patent is valid, and the cost of a lawyer, who can win?
J. S. Greenfield
>Phil Zimmerman acknowledges that his PGP software infringes the RSA patent(s),
>but he hasn't had his ass kicked yet (he almost did, but thats not the point).
PGP *once* infringed the patent. The current (official) US version of PGP
does not. (Of course, foreign versions *never* infringed the patent...)
Even before the latest version, there was a properly licensed version of PGP
available from ViaCrypt, for organizations that could not, or would not,
take theire chances in violating the patent.
J. S. Greenfield
>I think I should clarify my point here. Suppose you patent an
>algorithm for one NP-complete problem. Now I find an isomorphism of
>your patented algorithm that solves a different NP-complete problem,
>and a transform between the input data in your NP-complete problem
>and my NP-complete problem. Now I apply the transform and
>isomorphism to the same application that you have a patent for,
>but by transforming the algorithm and data to another domain I am
>using a "different" algorithm. Now am I infringing?
I'm not knowledgeable enough of the details of patent law to give you
a definitive answer.
The *general* standard of patent protection is that a patent must
provide sufficient information for a practioner skilled in the art to
be able to produce the patented invention. Novel applications generally
do *not* infringe existing patents, and are even eligible for patent
protection, themselves.
The crux of your question would seem to revolve around whether a particular
isomorphism is sufficiently well-known to practitioners killed in the
are, to allow them to easily derive the related algorithm. That's
obviously situation dependent. In the example at hand, namely NP-complete
problems, it's well-know within the field that such isomorphisms exist
(since a problem can't be called NP-complete until it is proven that
such an isomorphism exist...)
>For another example, suppose X patents an algorithm for putting a
>signature on an image by using convolution to apply a notch filter
>to the image. But suppose they don't know they could perform the
>same function by multiplying the Fourier transforms of the image
>and their convolution kernel, so they fail to claim transform
>multiplcation in their patent. (Of course they probably would
>know, but this is only an example; there are many unknown duals
>for any algorithm.) Now suppose Y writes a program that puts a
>signature on an image by multiplying the FFT of the image and the
>FFT of the same mathematical function X uses for a convolution
>kernel, thus applying the same notch filter. Here Y is using the
>"same" algorithm as X, but in a different spatial domain. Is Y
>infringing X's patent?
I don't believe that these two algorithms qualify as the same algorithm.
As I recall from my days as a EE, one often specifically transforms
domains in order to reduce the complexity of a computation (for example,
reducing a convolution of signals to a simple product).
The fact that the two algorithms compute the same result does not make
them equivalent in terms of patent. If it did, then patenting a single
algorithm for some given problem (say, convolution of two signals), would
effectively provide a patent on the *computation* itself. Consequently,
I'd expect that a patent on a particular algorithm to compute convolutions
(presumably for some particular application(s)) would protect only that
algorithm, and trivial variations.
(In this case, I'd say that transforming domains, though well-known, is
not a trivial variation of a direct convolution algorithm.)
>Furthermore, how can any reasonable patent search work in
>such cases unless the lawyers doing the search also have
>degrees in computation theory, image processing, etc.?
Remember that in order to be admitted to the patent bar (in order to be
able to prosecute applications), an individual must have a technical
degree from a list of approved degrees. (One of the problems is that
computer science is *not* currently one of those degrees. The PTO is
currently experimenting with CS-trained examiners. The results of that
will determine whether the patent bar is opened up to CS degrees.
In any case, to answer your question, a party would be ill-advised to
deal with a patent lawyer, or other individual, who does not have
expertise in the particular field (or fields) relevant to the search.
This isn't specific to algorithms. It's true of all patent work. Most
patent lawyers do specialize in the fields that they have studied. My
IP lawyer, for example, was trained as a EE/CE, so he specializes in that
area. He undoubtedly will occasionally do work in other areas, if the
patents are fairly simple, but the bulk of his work has to do with EE/CE-
related patents.
>Do these questions serve to demonstrate that software patents
>may possibly be different from other patents on processes?
>(Wasn't that your original challenge?) Doesn't the fact that
>you can transform one algorithm/domain into another make you
>a bit uneasy?
Not particularly. The basic approach seems clear, and is the same
as for other technologies. If the new application is trivial or well-
known, then it probably ought to be covered by the patent. If, on
the other hand, the application is novel, then it ought not be covered
by the patent.
>>>This consideration is made more vivid by the
>>>proposition made earlier that we use an algorithm equivalent but
>>>unequal to LZW to resolve the GIF conflict.
>>
>>Well, I don't know what "equivalent but unequal" means.
>
>It means what I described above. This is a complex issue to me,
>so I hope I've articulated my point in a comprehensible way.
What I'm saying is that I don't know what is being proposed as an
"equivalent but unequal" algorithm, so I can't form an opinion as to whether
or not it would infringe the LZW patent.
J. S. Greenfield
>>It does not make sense to draw general conclusions about how the patent
>>system *must* function for algorithms, on the basis of practical
>>experience with a patent office that is not currently prepared to handle
>>algorithms.
>
>Algorithm patents put a 20-year (approx) ball and chain on the
>software industry.
And that's not true of other patents?
>For the 17 years the patent runs, only medium to large
>size developers can use it, because the very small ones can't afford the
>administrative fees associated with the royalties-- even if the royalties
>themselves are very small. If there are enough algorithm patents, very small
>developers are put completely out of business, and medium sized ones operate
>at a severe disadvantage-- the small ones because they can't afford the patent
>searches, and the medium sized ones because they don't have enough "chips" of
>their own to use the patents for free.
Imminent death of the small-time software industry predicted. Film at 11.
>Worse, there's the "submarine patent" problem-- an algorithm can be
>independently reinvented and in wide use before a patent on it is granted.
>When that patent is granted, the re-inventor is stuck, denied the right to his
>own invention. IMO this happens far more often in the fast-moving software
>industry than in other industries. It could be solved, but only by having the
>patent office take a much shorter time to grant patents. And that they
>aren't going to do.
And that's not true of other patents?
As I've said before, there unquestionably needs to be some adjustment
in the evaluation of patents--in order to weed out trivial algorithms (i.e.,
algorithms that are likely to be frequently rediscovered) and well-known
algorithms much better than the current batch of ill-prepared examiners
have been able to do.
No matter how many times somebody proclaims that the patent system is
incapable of functioning for algorithms--on the basis of nice theories and
experience with the current system--I ain't gonna be convinced.
Let's remember that the first great triumph of Information Theory was the
proof that FM broadcast could never work...
>And, of course, there's the ridiculous claims which are essentially unbeatable
>because the patent holders have better lawyers than the challengers-- RSAs
>claims to all public key encryption, for example.
Nobody claims that the legal system is great. We all know it has serious
pitfalls.
Of course, in this particular case, I wouldn't worry about it. The *idea*
of a public-key cryptosystem clearly cannot be patented. It doesn't matter
what PKP claims. It doesn't hold a patent on it.
If you go out and invent a new cryptosystem, one of two situations will
exist. Either 1) the system will be of little practical interest--in which
case, PKP won't be interested enough to sue you anyway, or 2) the system
will be of significant practical interest, in which case the commercial
value of the system will justify any costs associated with fighting PKP,
should they sue.
Sure, you shouldn't *have* to deal with such matters--but hey, life ain't
always fair, and that's how life is in the big city. The problem of
frivilous, intimidating litigation is by no means limited to algorithm
patents, or even algorithms.
(And I say that as somebody who has actually *been* affected by such problems
with the legal system...)
John Nagle
>In article <MIB.95Ja...@churchy.gnu.ai.mit.edu> m...@churchy.gnu.ai.mit.edu (Michael I Bushnell) writes:
>>But given two computer programs, you cannot tell whether they do the
>>same thing by any automated process. Sometimes, two programs do the
>>same thing, but there exists no proof of that fact.
>>
>>This is a trivial application of Turing's Halting Theorem. I thought
>>you were an "expert". Are you unaware of this theorem?
That's a misunderstanding of the halting problem. It's possible
to construct such programs, but it's hardly the normal situation.
Programs for which halting is undecidable tend to be useless, anyway.
Besides, the halting problem is formally decidable for any deterministic
machine with finite memory. Think about it; either you repeat a
previous state, and are thus in a loop, or you halt, in finite (yes,
maybe big, but finite) time.
The halting problem just isn't an issue in software patents.
John Nagle
Darin Johnson
> cryptography or not. :) I don't think that the publication of "public"
> keys is the key element of public-key cryptography (no pun intended). I
> think the idea of having separate keys for encryption and decryption is the
> critical element. They would need to have conjured up that idea before
> they could have invented RSA.
That's not a big leap though. That's important in Diffie and Hellman
but possibly (not having read it) the focus was more on distribution
of keys in possibly insecure medium. Ie, there needed to be a way
to have a separate key that didn't need to be secured from prying
eyes. That's much much more important than merely having two keys.
I think having two keys was used long before then (although I can't
think of any methods where the second key is not a transformation of
the first). Mathematically, encryption and decryption were always
treated as separate functions, so why not the keys?
So what's in RSA:
- explicitly wishing to find an appropriate algorithms to satisfy
Diffie and Hellman. Diffie and Hellman basically said that if
you can get an encryption algorithm with these properties, then
you can do such and such with it.
- a method to determine if a very very large number is likely to
be a prime or not. This is the important part. It allows you
do generate a number with only 2 prime factors. (very large
means 10^100 or greater)
- an encryption method that uses the above (and that uses the above
to generate the real keys). Nothing fancy or obscure to anyone
familiar with cryptography or number theory. It just satisfies
the requirements of Diffie and Hellman.
The snag part is that how RSA is done is widely known. It's studied
by many undergrads. The prime factorization by itself is probably
studied in number theory without concern for cryptography. Anyone
can sit down and code this up with a little work. The questions are
whether or not coming up with a new way to generate large primes and
using this with the encryption algorithm is in violation of the patent
or not. Or if you can use the method to generate large primes and
then use your own encryption method. I think PGP does the former
but I'm not sure. Certainly I think that the RSA patent is valid and
should hold, but how much can this be changed until you can safely
say you have an algorithm that isn't covered by the patent?
--
Darin Johnson
djoh...@ucsd.edu
Where am I? In the village... What do you want? Information...
J. S. Greenfield
Please be careful with your citations. From the way you've quoted, it
might appear to some that you are responding to my post, when in fact, you're
responding to Mr. Bushnell's post.
My posts, in fact, agreed precisely with your comments about the relation
between the theoretical results about halting, and the practical experiences
of real life...
Darin Johnson
No. But don't make the mistake of assuming that CS started only
once computers were invented. Many algorithms came about in order
to make it feasible to have a group of humans work on calculations
more efficiently (ie, to design large books of numbers so that one
could calculate project trajectories). CS is a very old field
really, or more accurately, it is a combination of very old fields
and very new fields (a grab bag really).
The ironic part is that after the invention of computers, many of
these algorithms were somewhat forgotten for awhile. Many of those
calculation methods would have taken much longer on a serial computer
because they involved many parallel calculations and involved a lot
of redundancy and error checking on the side (because humans have a
high error rate). But with parallel computation suddenly these
forgotten methods were reused or rediscovered.
--
Darin Johnson
djoh...@ucsd.edu
Gravity is a harsh mistress - The Tick
J. S. Greenfield
>> I concede that there are differences. But you will have to concede that we
>> do not have the practical experience--with a patent system that is
>> *prepared* to handle the technology--to conclude that patents are inherently
>> inimical, rather than beneficial, to the field.
>
>Well, apart from the fact that the proposed experts examining those
>patents do neither address the lifetime problem, nor the cost problem (how
>much money would *you* invest in patent searches for a freeware program?),
>it is *very* doubtful if it will *ever* be possible to *have* such
>experts.
I'm sorry, but I just can't follow what you're trying to say here. Can you
try restating it?
>Of course, there will always be people qualified to do this. However, I
>very much doubt that there will ever be enough of them to man the patent
>offices in the first place; and then I doubt that the government will pay
>enough to attract them.
Well, only time can tell that. However, I think there's plenty of reason
to expect that qualified people can be attracted to such positions. For
one thing, we know that sufficiently qualified people in *other* technologies
have been attracted to examiner positions. What's more, there are *tons*
of degrees being produced in CS. The US produces approximately 1000 CS
PhD's each year. The numbers for Masters and Baccalaureate degrees must
be enormous.
There would seem to be a good chance that some of the many computer
scientists will decide to change fields. Patent law is a very common path
for technical folks to go if they have interests in law, and working as a
patent examiner for a few years offers the advantages of strong experience,
automatic admission to the patent bar, and excellent prospects for finding
subsequent employment with good patent firms.
We definitely cannot conclude that qualified examiners cannot be attracted
until we see that such problems actually happen, in practice.
J. S. Greenfield
>> Well, I'm not too concerned with whether they called it "public-key"
>> cryptography or not. :) I don't think that the publication of "public"
>> keys is the key element of public-key cryptography (no pun intended). I
>> think the idea of having separate keys for encryption and decryption is the
>> critical element. They would need to have conjured up that idea before
>> they could have invented RSA.
>
>That's not a big leap though. That's important in Diffie and Hellman
>but possibly (not having read it) the focus was more on distribution
>of keys in possibly insecure medium. Ie, there needed to be a way
>to have a separate key that didn't need to be secured from prying
>eyes. That's much much more important than merely having two keys.
>I think having two keys was used long before then (although I can't
>think of any methods where the second key is not a transformation of
>the first). Mathematically, encryption and decryption were always
>treated as separate functions, so why not the keys?
Well, I'm unaware of separate key cryptosystems predating Diffie and Hellman's
suggestion for such. That doesn't say they don't exist, just that I don't
know of them.
Upon thinking a bit more about, however, I agree that the fact that one key
(the encryption key--or what we commonly think of as the public key)
cannot be used to determine the other key (the decryption key), is a critical
element as well.
What I really meant to get at was that I didn't think that the idea of
(actually or effectively) publishing one key was a critical element. If the
NSA developed public-key cryptography, but never intended to make any keys
"public," I wouldn't care one whit. The significance of the discovery would
seem just as great, to my eye.
>So what's in RSA:
> - explicitly wishing to find an appropriate algorithms to satisfy
> Diffie and Hellman. Diffie and Hellman basically said that if
> you can get an encryption algorithm with these properties, then
> you can do such and such with it.
Well, I don't think this is appropriately termed part of RSA. This was
Diffie and Hellman's contribution, not RSA's contribution.
> - a method to determine if a very very large number is likely to
> be a prime or not. This is the important part. It allows you
> do generate a number with only 2 prime factors. (very large
> means 10^100 or greater)
RSA did not contribute prime generation algorithms, either. The most
important algorithms for such are based on the contributions of Solvay
and Strassen, and Miller and Rabin.
> - an encryption method that uses the above (and that uses the above
> to generate the real keys). Nothing fancy or obscure to anyone
> familiar with cryptography or number theory. It just satisfies
> the requirements of Diffie and Hellman.
RSA is, indeed, deceptively simple. The computations involved, though
quite slow, are very straightforward. But the fact remains that
Rivest, Shamir and Adleman (well, really just Rivest) were the ones
who came up with the scheme, and saw the application to public-key
cryptography. And the fact remains that this discovery turned out to
be fairly monumental within the cryptography world.
>The snag part is that how RSA is done is widely known. It's studied
>by many undergrads. The prime factorization by itself is probably
>studied in number theory without concern for cryptography.
Factorization has always been of some interest to number theorists,
but RSA is responsible for spawning most of the work done in
factoring over the last 15 years or so.
>Anyone
>can sit down and code this up with a little work. The questions are
>whether or not coming up with a new way to generate large primes and
>using this with the encryption algorithm is in violation of the patent
>or not.
I know of no patents pertaining to any of the prime generation algorithms
currently in use. You can generate all the primes you want, without
fear of infringement.
Using the RSA encryption and decryption algorithms is a different story.
Those you can use all you want for research purposes. If you want to make
commercial use of the algorithms (in the US), on the other hand, you'd better
1) be too small for them to pursue the infringement, 2) be working for the
government (which, as I said previously, has a royalty-free license to
use the algorithms), 3) be using the properly licensed, but freely
available RSAREF package, 4) be an individual licensee, or 5) be prepared
for some major legal problems.
>Or if you can use the method to generate large primes and
>then use your own encryption method. I think PGP does the former
>but I'm not sure.
PGP almost certainly uses the standard Miller-Rabin method to generate
primes. As I said before, that requires no licensing, because it's not
patented.
PGP certainly does use RSA encryption. There is no significant factoring-based
alternative ecryption method. That's precisely why so many folks are
upset about restrictions on RSA.
Anybody who tries to develop and use their own method--with first subjecting
it for peer review--is simply crazy.
>Certainly I think that the RSA patent is valid and
>should hold, but how much can this be changed until you can safely
>say you have an algorithm that isn't covered by the patent?
There aren't any known, RSA-like algorithms around that are worth using
and which are not covered by the patent. I believe that there is still
one Knapsack algorithm in use (though undoubtedly patented), it's probably
not of much interest to most folks.
If you want to use a good, patent-free, public-key algorithm prior to
September 20, 2000, you (or someone else) will have to discover it yourself,
and leave it in the public domain.
If you should, be sure to let the rest of us know. :)
Charles Owen
getting disgusted. There is NO THEOREM which says that you can't
tell if a computer program halts. There is NO THEOREM which says
that you can't tell if two computer programs do the same thing. Sorry,
folks, but I can give counter examples if you like. The theorems
all say that there exist programs which you can't tell are the
same or can't tell if they will ever stop. I can
give you an example of a Turing machine which I can prove halts. I
can give you an example of two Turing machines which I can prove
identical (given the same input they give the same output).
Besides, real computers are not equivalent to Turing machines. No
infinite tape or memory! The Halting Theorem does not apply. It is
always possible to determine is a program will halt since there are
a finite number of states in a finite computer (admitedly a VERY
VERY large number.
As for comparing computer programs in the patent office, there is
just not that much of a problem to compare two algorithms to
determine if they are equivalent. Do they produce the same
output for the same input? Do they have equivalent intermediate
states? Is the asymptotic running time equivalent? The DCT and
the FFT are not equivalent. One if O(nlogn) the other is O(n^2)
(you did not say "fast DCT"). Even the fast examples are
significantly different in their internal states. But, give me
two implementations of quicksort, allbeit in totally different
languages, and I can tell you that they are both quicksort.
Kai Henningsen
> I concede that there are differences. But you will have to concede that we
> do not have the practical experience--with a patent system that is
> *prepared* to handle the technology--to conclude that patents are inherently
> inimical, rather than beneficial, to the field.
Well, apart from the fact that the proposed experts examining those
patents do neither address the lifetime problem, nor the cost problem (how
much money would *you* invest in patent searches for a freeware program?),
it is *very* doubtful if it will *ever* be possible to *have* such
experts.
Of course, there will always be people qualified to do this. However, I
very much doubt that there will ever be enough of them to man the patent
offices in the first place; and then I doubt that the government will pay
enough to attract them.
Kai
--
Internet: k...@ms.maus.de, k...@khms.westfalen.de
Bang: major_backbone!{ms.maus.de!kh,khms.westfalen.de!kai}
## CrossPoint v3.02 ##
Kai Henningsen
> And you don't think that *either* one could characterize the O(n^2)
> algorithm as pretty mundane and the O(n) algorithm as much more interesting?
>
> I'm sorry, but this argument just doesn't cut it for me. Finding great
> algorithms is often the result of momentary inspiration, but so what.
> Many people can recognize a great idea, even if they couldn't have
> developed the idea themselves.
Well, it's happened to me lots of times - I look at a problem, sleep on
it, say "there's no nice solution", and code an ugly O(n^2) one. Then,
maybe a year later, I get back to the problem, look at it, think for five
minutes, and say "nonsense, I can do that in O(n)", and code it in 10
minutes.
So, was this anything patentable? Of course not. It's trivial. On the
other hand, it obviously *was* a problem of looking at the problem in a
certain way.
To put it another way: I don't think that Columbus' solution to the egg
problem should rate a patent.
However, the problem for the patent examiner is that he *starts* with the
solution. I don't think it's in any way obvious how hard it may have been
to find the solution, and how hard it will be for someone different to
find it again.
Kai Henningsen
> If the true useful life span is considerably longer than the patent life
> span, I expect many creators will take their chances. After all, if the
> life span is short, they may not see much of a threat from having to
> pay license fees (for a short while) if someone else comes along later,
> and patents the invention. What's more, if they're maintain the algorithm
> as a trade secret, they will likely not worry about a subsequent discoverer
> even *knowing* that they are using the same algorithm.
The more I think about it, the more attractive it sounds.
Tom Tromey
JS> I have merely argued that 1) we can give little weight to our
JS> current, short- lived experience with a patent system that we
JS> *know* is ill-suited to handle algorithms, and 2) we probably
JS> ought to give considerably more weight to our much longer-lived
JS> experience with the patent system being fairly successful for
JS> other technologies, which it has handled traditionally and, hence,
JS> has been better prepared to handle.
Well, this makes sense as far as it goes. But you are ignoring that
software patents are relatively new; they first started appearing in
the 80's. Until that time, algorithms were unpatentable, and yet
somehow they were developed nonstop. What I'm really trying to say
here is that the "burden of proof" of the necessity of patents should
be on those desiring patents. Patents are not a natural right, like
the freedom of speech. Patents are granted for a specific reason,
namely to further science and the useful arts. But if algorithms
continue to be developed in the absence of software patents, then why
allow them at all? How will software patents aid progress?
Tom
--
tro...@cns.caltech.edu Member, League for Programming Freedom
"Sadism and farce are always inexplicably linked"
-- Alexander Theroux
Tom Tromey
>> In article <3f13j0$p...@hermes.synopsys.com> jb...@synopsys.com (Joe Buck) writes:
>> Patents in other fields are likely to have different tradeoffs. In
>> software, the economics are such as to make patents particularly
>> damaging. Software is an area that used to have a very low barrier
>> to entry: a talented and motivated middle-class college student
>> could get into business. Software patents are ending that. In a
>> very short time, you won't be able to be in business without a
>> portfolio of patents to cross-license, meaning that only
>> established companies can play.
JS> I don't argue that the trade-offs don't differ for different
JS> technologies. I just argue that 1) we can't wholly ignore the
JS> issue of systemic benefits provided by the patents system (as
JS> Stanton suggested), and 2) we can't reasonably evaluate the
JS> trade-offs for algorithms based solely upon the practical
JS> experience with the current PTO (as many have been suggesting in
JS> this thread).
I agree that basing anti-software-patent arguments on the mistakes of
the current PTO is leads to many specious arguments. However ignoring
the differing economic tradeoffs various fields is also an error. As
Joe Buck says, many people can start their own software company. Not
many people have the captial it takes to start a drug company on the
other hand. And, since creating a new drug is so very expensive (as
compared to the cost of manufacturing and distributing it), it makes
sense to provide patent protection for that field.
I'd be interested to hear what these "systemic benefits" of the patent
system might be. You make it sound as though software patents will
greatly benefit the field. The fact is, the software industry (read
"algorithm industry" if you like) flourished without the existence of
software patents. Saying that they are suddenly necessary strikes me
as absurd in the extreme.
J. S. Greenfield
>Well, this makes sense as far as it goes. But you are ignoring that
>software patents are relatively new; they first started appearing in
>the 80's. Until that time, algorithms were unpatentable, and yet
>somehow they were developed nonstop. What I'm really trying to say
>here is that the "burden of proof" of the necessity of patents should
>be on those desiring patents. Patents are not a natural right, like
>the freedom of speech. Patents are granted for a specific reason,
>namely to further science and the useful arts. But if algorithms
>continue to be developed in the absence of software patents, then why
>allow them at all? How will software patents aid progress?
and in another article...
>I'd be interested to hear what these "systemic benefits" of the patent
>system might be. You make it sound as though software patents will
>greatly benefit the field. The fact is, the software industry (read
>"algorithm industry" if you like) flourished without the existence of
>software patents. Saying that they are suddenly necessary strikes me
>as absurd in the extreme.
Well, first off, your history doesn't seem quite right. If I'm not mistaken,
IBM was granted a patent on DES in 1976, which means they would have applied
for the patent a few years earlier. (Yes, I know that patent wasn't
enforced...) The Diffie-Hellman and RSA patents were applied for in the
late seventies, though they weren't granted until '80 and '83, respectively.
So, I think a more accurate statement of the history of algorithm patents
would be that they date back to at least the mid seventies.
Interestingly enough, that corresponds pretty closely to the time when
computers were just beginning to become widespread. In the mid-seventies
computers start becoming more prevalent within businesses. It's really not
until the eighties that computers become commonplace within businesses,
and certainly not until then that they become commonplace in homes.
So what does that mean? Before algorithm patents, the application of
computer algorithms was quite limited in terms of its commercial value.
Since most algorithms had little potential commercial value, there was
little incentive to maintain them as trade secrets.
With the spread of computer technology, many algorithms took on significantly
more potential commercial value. That happens at the same time as, or
slightly after, the introduction of algorithm patents.
You ask what the systemic benefits of patents for algorithms are. The answer
is simple, because they are the same benefits that the patent provides for
other technology--namely, it provides an incentive to publish algorithms,
rather than maintaining them as trade secrets. The whole theory of the
patent system is that when inventions are published (rather than kept secret)
society benefits because knowledge is *shared* and others can build upon that
knowledge to advance the technology further. (You may dispute this theory,
but it is the theory of the patent system, nonetheless.)
So, historically, what we have is a period where most computer algorithms hold
relatively little commercial value--and therefore, little incentive to
maintain them as trade secrets--followed by a period where computer algorithms
held higher potential commercial values *and* had patent protection
available--thereby, discouraging the maintenance of them as trade secrets.
From this history, you draw the conclusion that patents offer no benefits.
That may well be the case...but the fact is that the history says nothing to
support that conclusion, contrary to your contention.
Of course, this isn't saying anything substantively different from what I've
said in many other posts. By now I'm getting pretty tired of repeating
myself. If you disagree with this, feel free to post your thoughts, but
don't count on me to offer a response. I don't have the impression that
there's anything more I can say that hasn't already been said, *many* times
over now...
Tim Smith
>Two people can start up a software company with about $30,000 capital
>and produce major profit, if they are talented programmers. Their new
>system might easily infringe hundreds of patents; they would have to
>search patent databases for thousands of possibly patented algorithms.
>Each patent search costs between $100 and $1000.
Can you give examples of the kinds of programs where this might happen?
The programmer would have to search for thousands of algorithms only if their
program contained thousands of new algorithms. What class of programs
contains so many new algorithms?
--Tim Smith
Paul Eggert
>Do you have a reference on the Gauss prior art? I'd love to have this
>one the next time the question comes up (actually quite regularly).
I vaguely remember that an article appeared on this subject (the FFT)
in _Science_ around 1990 or 1991. The previous art by Gauss was in
1805; he used the FFT to speed calculation of asteroid orbits (a hot
topic at the time).
Paul Eggert
> It seems to me that algorithm patents serve the same purpose as non-lagorithm
> patents--to encourage the creation and *sharing* of technical knowledge.
Actually, the purpose of the patent system is to promote progress, not
merely to share technical knowledge. And in this particular case, the
Unisys patent is discouraging progress instead of promoting it: the LZW
approach is not that much better than other unpatented approaches, and
Unisys is merely using their monopoly position to jump out of the weeds
and tax a market that would have used some other scheme had it known
that the patent would be an issue.
The most likely result of this brouhaha will be an expensive conversion
by the industry to some other format merely to avoid the patent. This
hardly constitutes progress. In fact, it is regress; we should be
encouraging clever people to work on new, useful things, instead of
wasting their time circumventing a patent that should not have been
granted in the first place.
> Remember that, in the absence of patent protection, a creator who wishes
> to protect his invention is left only with trade secret protection.
You've omitted copyright, the principal (and to society, the most useful)
form of intellectual property in software. Before software patents
became popular, the software industry survived and prospered by using
copyright protection. For example, Microsoft and Oracle grew from
nothing to colossi primarily using copyright protection (with trade
secret also being important, of course; but patents were hardly on the
radar screen at all). Patents are not needed for progress in software;
on the contrary, our early experience with them is that they tend to
_discourage_ progress.
> that there is no substantive philosophical difference between
> patents for algorithms and non-lagorithmic processes
This argument suggests that you are more interested in the theory or
philosophy of patents than in their practice. But most of the people
in this forum are more concerned with their practical effects, and if
the practical effects of a class of patents are harmful, then most
people would agree that we shouldn't allow those patents. This is
why, for example, surgical methods are not patentable: their harms
would outweigh their benefits.
But even if we limit ourselves to patents in theory (as opposed to
practice), your assertion ignores important differences between
mathematical and physical procedures. In the past, we did not allow
patents on mathematical procedures like Gaussian elimination, and we
did allow them on physical procedures like rubber-curing. There were
good reasons for this distinction: for example, mathematical procedures
are too broadly applicable and too flexible to be appropriate subjects
for legal monopolies, and it is often impractical to determine whether
someone else is using ``your'' mathematical procedure.
But now that computers have blurred the distinction between the two
arenas, we must decide more carefully where to draw the line between
mathematics and physical processes. Unfortunately, our first attempts
to do so have been dominated by patent lawyers, who have a vested
interest in promoting patents on everything, regardless of whether it
is in society's best interest overall. This has led to unfortunate
consequences like the Unisys LZW patent.
Jefferson Ogata
>In article <ogataD2...@netcom.com> og...@netcom.com (Jefferson Ogata) writes:
>>But consider this: it does take a fair amount of training to even
>>understand how the FFT (for example) works. In general, truly
>>innovative algorithms that represent a significant work investment
>>will be fairly complex. The abstractness of algorithms and the
>>existence of dual equivalents make many of them difficult to
>>understand and compare. For example, suppose someone patented an
>>algorithm for finding the convex hull of a set of points. If I
>>converted the algorithm to its dual (calculation of a voronoi
>>region) would I be infringing the patent? The algorithms are
>>equivalent.
>
>My understanding of patent law is that an algorithm cannot be patented
>(i.e., *should* not be granted a patent) unless it is applied to a
>particular application or class of applications. Consequently, one should
>not be able to patent a convex hull algorithm, alone. One could,
>potentially, patent a convex hull algorithm for use in, say, constructing
>CT images.
>
>It should not infringe the patent to use the same convex hull algorithm
>for an application not covered by the patent. If an equivalent algorithm
>for calculating a voronai region is used for an application not covered
>by the patent (i.e., a novel application), I would not expect it to be an
>infringing use.
I think I should clarify my point here. Suppose you patent an
algorithm for one NP-complete problem. Now I find an isomorphism of
your patented algorithm that solves a different NP-complete problem,
and a transform between the input data in your NP-complete problem
and my NP-complete problem. Now I apply the transform and
isomorphism to the same application that you have a patent for,
but by transforming the algorithm and data to another domain I am
using a "different" algorithm. Now am I infringing?
For another example, suppose X patents an algorithm for putting a
signature on an image by using convolution to apply a notch filter
to the image. But suppose they don't know they could perform the
same function by multiplying the Fourier transforms of the image
and their convolution kernel, so they fail to claim transform
multiplcation in their patent. (Of course they probably would
know, but this is only an example; there are many unknown duals
for any algorithm.) Now suppose Y writes a program that puts a
signature on an image by multiplying the FFT of the image and the
FFT of the same mathematical function X uses for a convolution
kernel, thus applying the same notch filter. Here Y is using the
"same" algorithm as X, but in a different spatial domain. Is Y
infringing X's patent?
If your answer is yes, then a patent on one algorithm for an
application may end up applying to another application simply
because there is a transform taking you between the first
algorithm/application and the second algorithm/application.
I think this is unacceptable. A patent holder can claim that a
third party who is handling a completely different application
is infringing because they are using an isomorphism to the
patented algorithm, therefore they are theoretically solving
the same problem.
If your answer is no, the patent only applies to what is in
the claims, then how would a patent holder defend a patent if
someone does derive a transformed algorithm directly from
the patented algorithm, thereby infringing in spirit?
Furthermore, how can any reasonable patent search work in
such cases unless the lawyers doing the search also have
degrees in computation theory, image processing, etc.?
Do these questions serve to demonstrate that software patents
may possibly be different from other patents on processes?
(Wasn't that your original challenge?) Doesn't the fact that
you can transform one algorithm/domain into another make you
a bit uneasy?
>>This consideration is made more vivid by the
>>proposition made earlier that we use an algorithm equivalent but
>>unequal to LZW to resolve the GIF conflict.
>
>Well, I don't know what "equivalent but unequal" means.
It means what I described above. This is a complex issue to me,
so I hope I've articulated my point in a comprehensible way.
--
Jefferson Ogata og...@netcom.com
"Animals without backbones hid from each other or fell down. Clamasaurs and
oysterettes appeared as appetizers. Then came the sponges, which sucked up
about ten percent of all life." - Firesign Theatre
Seth Finkelstein
Easy. Any graphics viewer/editor program. It's not "*new*"
algorithm, but algorithms that are patented. We've been discussing XOR
cursors and GIF just off the top. There's also RLE format. Now let's get
into fast algorithms for scaling, rotating, color quantization. How
about display buffering? Note getting the techniques out of a standard
text does not help, because the text has no obligation to mention that
these algorithms have been patented, or have patent-unencumbered ones.
Or even if there is a stock piece of code, the programmer must worry
that every speedup or customization might possibly infringe.
One point that deserves more emphasis is that algorithm
patenting is a back-door to format patenting. That's what we've seen in
GIF. All you do is to come up with a not obvious "process", (it doesn't
have to be *good*, it just has to pass the standard), then define
your format to be the data passed through that process. Bingo, anyone
who wants to read the files has to do the "process", and so must license
the patent. Reverse-engineering is no defense, because the "process"
itself is what's protected.
A standard graphics tool might deal with a dozen different
formats. Imagine if a license for each one needs to be negotiated (At
1.5% of the gross price! - note Compu$erve wants points off the *gross*,
not the *net*, that's like 10-15% of the profits otherwise). This will
totally destroy the small developer, and forget about freeware.
It needs to be emphasized: If algorithms are treated like
manufacturing processes, then the software market will end up looking
like industrial manufacturing (i.e. dominated by large capital outlays
needed for development costs).
--
Seth Finkelstein se...@mit.edu
Disclaimer : I am not the Lorax. I speak only for myself.
(and certainly not for Project Athena, MIT, or anyone else).
Alan Cox
>I still can't see how this "flies in the face" of the purpose of the patent
>system. Inventors of non-algorithmic processes must also search the prior
>art for potential infringements.
1. Algorithms are discovered not invented. They are pure statements of
mathematical logic. It becomes more of a complex issue when they result in
something that goes beyond that.
2. Computing systems are so complex a current patent search is not
economically viable. Its better to be very big and buy the problem out or
set up tons of small companys and just fold any that get sued
There is a third issue of suitability for patenting that I think is seperate
- stuff like the XOR cursor that no competent patent examiner should have
passed - thats stupidity and incompetence in the fact of new technology and
is nothing new in any area of law or politics.
>Remember that, in the absence of patent protection, a creator who wishes
>to protect his invention is left only with trade secret protection.
Its not an invention - its a discovery, and as a mathematical fact its like
patenting 'add one' or divide by 22. The XOR patent is basically the fact
that
((A XOR B) XOR B) = A
There is a further issue which is that in computing the US patent system is
being abused beyond its original intention by companies. The fact that the
computing industry changes so fast that the patent time is too long does not
help this. Look at things like encryption in the USA - patents are stopping
it. A patent is a monopoly to exploit. With the times currently uses, the
idiocy of patents granted and the ability to use patent claims however
dubious to impede the competition the patent is being used as a monopoly
building system and a tool for harrasing your competition not for
sharing of ideas and ensuring you still claim back your development costs
reasonably..
The EEC doesn't recognize the idea of software patents. Instead a wide
variety of other protections can be applied (copyright of images [ not
generic classes of such!]). Unfortunately the UK government seems to want
to try and change this.
Alan
--
..-----------,,----------------------------,,----------------------------,,
// Alan Cox // iia...@www.linux.org.uk // GW4PTS@GB7SWN.#45.GBR.EU //
``----------'`--[Anti Kibozing Signature]-'`----------------------------''
One two three: Kibo, Lawyer, Refugee :: Green card, Compaq come read me...
Matthew Russotto
>In article <1995Jan12....@picker.com> russ...@ariel.ct.picker.com (Matthew Russotto) writes:
>
>>>It does not make sense to draw general conclusions about how the patent
>>>system *must* function for algorithms, on the basis of practical
>>>experience with a patent office that is not currently prepared to handle
>>>algorithms.
>>Algorithm patents put a 20-year (approx) ball and chain on the
>>software industry.
>And that's not true of other patents?
Other industries don't move so fast that 20 years is an eternity. Or perhaps
the lack of applicability of the patent system to software (until recently)
has been what has kept that industry moving fast.
>>For the 17 years the patent runs, only medium to large
>>size developers can use it, because the very small ones can't afford the
>>administrative fees associated with the royalties-- even if the royalties
>>themselves are very small. If there are enough algorithm patents, very small
>>developers are put completely out of business, and medium sized ones operate
>>at a severe disadvantage-- the small ones because they can't afford the patent
>>searches, and the medium sized ones because they don't have enough "chips" of
>>their own to use the patents for free.
>
>Imminent death of the small-time software industry predicted. Film at 11.
Yeah, you can jeer-- but that's not a counterargument.
>>Worse, there's the "submarine patent" problem-- an algorithm can be
>>independently reinvented and in wide use before a patent on it is granted.
>>When that patent is granted, the re-inventor is stuck, denied the right to his
>>own invention. IMO this happens far more often in the fast-moving software
>>industry than in other industries. It could be solved, but only by having the
>>patent office take a much shorter time to grant patents. And that they
>>aren't going to do.
>
>And that's not true of other patents?
>No matter how many times somebody proclaims that the patent system is
>incapable of functioning for algorithms--on the basis of nice theories and
>experience with the current system--I ain't gonna be convinced.
>Let's remember that the first great triumph of Information Theory was the
>proof that FM broadcast could never work...
You aren't willing to accept theory, and you aren't willing to accept
experience, so clearly you aren't willing to accept any argument. Why do you
bother asking? For years the software patents granted have been
hanging over the industry's head-- now, one of them has come crashing down,
and still you refuse to recognize the problem. Even with decent patent
examiners, LZW would have been patented.
>>And, of course, there's the ridiculous claims which are essentially unbeatable
>>because the patent holders have better lawyers than the challengers-- RSAs
>>claims to all public key encryption, for example.
>Nobody claims that the legal system is great. We all know it has serious
>pitfalls.
>Of course, in this particular case, I wouldn't worry about it. The *idea*
>of a public-key cryptosystem clearly cannot be patented. It doesn't matter
>what PKP claims. It doesn't hold a patent on it.
>If you go out and invent a new cryptosystem, one of two situations will
>exist. Either 1) the system will be of little practical interest--in which
>case, PKP won't be interested enough to sue you anyway, or 2) the system
>will be of significant practical interest, in which case the commercial
>value of the system will justify any costs associated with fighting PKP,
>should they sue.
The cost of fighting a patent is so high that fighting PKP might not be worth
the potential gains-- or might simply not be possible even if the inventor
wanted to risk it. Patents raise the cost of entry in software, just as they
do in other industries. The main difference is that the cost of entry in
software is near zero (a few thousand bucks of computer equipment) without
patents-- so patents become an overriding factor.
>Sure, you shouldn't *have* to deal with such matters--but hey, life ain't
>always fair, and that's how life is in the big city. The problem of
>frivilous, intimidating litigation is by no means limited to algorithm
>patents, or even algorithms.
The case of patents is the only one where the defendant starts out at a
serious legal disadvantage-- the presumption that the claims are valid.
Max Hailperin
m...@geech.gnu.ai.mit.edu (Michael I Bushnell) writes:
... It is the case, however, that it is not generally
possible, given two algorithms, to tell whether they even solve the
same problem or not, let alone whether they do it in the same way.
(It's a simple conclusion from Turing's work.) ...
Without taking a stand on algorithm/software patents, let me point out
that there is a fallacy in the above reasoning. The "even" and "let
alone" parts strongly suggest a claim that determining whether two
algorithms "do it in the same way" is strictly harder than determining
"whether they ... solve the same problem or not." This is not so. It
may well be *easier* to determine whether or not two algorithms "do it
in the same way" than whether they achieve the same end result. In
particular, the former may well be decidable, while the latter, as
Bushnell notes, is not. I say "may well be" because this depends on
the precise definition of "do it in the same way". There are
certainly reasonable definitions of that phrase which are decidable.
-Max Hailperin
Assistant Professor of Computer Science
Gustavus Adolphus College
St. Peter, MN 56082
Seth Finkelstein
>Well, first off, your history doesn't seem quite right. If I'm not mistaken,
>IBM was granted a patent on DES in 1976, which means they would have applied
>for the patent a few years earlier. (Yes, I know that patent wasn't
>enforced...) The Diffie-Hellman and RSA patents were applied for in the
>late seventies, though they weren't granted until '80 and '83, respectively.
>So, I think a more accurate statement of the history of algorithm patents
>would be that they date back to at least the mid seventies.
I think we need to distinguish between *theory*, as to when they
were sought, and *application*, when serious attempts were made to
enforce them. The theory dates back much earlier than the application,
and for a while, was pretty much ignored in practice (with notable
national-security type exceptions, where there are big problems also
with ITAR).
>So what does that mean? Before algorithm patents, the application of
>computer algorithms was quite limited in terms of its commercial value.
>Since most algorithms had little potential commercial value, there was
>little incentive to maintain them as trade secrets.
Ah, but they had little potential commercial value ALSO because
it was unclear that they could be considered property. So, more attempts
at making them property increase their value, and so spur even further
attempts. This goes along with the growth of the market, true, since if
they are property, an expanding market makes them better property. So we
mostly agree on this point, but there are certain differences in
emphasis. The question is more whether this type of patent would help
society or represent an attempt to abuse the system get an *undeserved*
monopolistic stronghold on parts of the market.
>You ask what the systemic benefits of patents for algorithms are. The answer
>is simple, because they are the same benefits that the patent provides for
>other technology--namely, it provides an incentive to publish algorithms,
>rather than maintaining them as trade secrets. The whole theory of the
But, UNLIKE other technology, the abstract notion of "process"
is so wide that it encompasses much within the concept that it is quite
different from other trade-offs, such as in industrial processing. In a
factory, no-one else can use your process to make widgets. Not too big a
deal. In software, no-one can read or write GIF files without paying
you. That's a big jump. In another article, I went on at length at how
algorithm patents are back-doors to format patents.
>patent system is that when inventions are published (rather than kept secret)
>society benefits because knowledge is *shared* and others can build upon that
>knowledge to advance the technology further. (You may dispute this theory,
>but it is the theory of the patent system, nonetheless.)
But a concomitant part of this theory is that the invention
would more likely be *lost* without the incentive to share. That has the
net effect that it grants a monopoly to the first person to get a patent.
Where the invention is *likely* to be redeveloped independently, this
means that the monoply is unneeded and counter-productive.
Why don't we have "journal paper patents"? One can run the same
line - it would encourage people to publish research. Imagine the
royalties on E=mc^2! Why should computer-oriented mathematicians get all
the profits? Why shouldn't physicists, chemists, etc be able to patent
their equations and discoveries? After all, those are often calculational
processes too. Every journal paper is *by definition* not obvious to one
skilled in the field, so we don't even have that argument.
>So, historically, what we have is a period where most computer algorithms hold
>relatively little commercial value--and therefore, little incentive to
>maintain them as trade secrets--followed by a period where computer algorithms
>held higher potential commercial values *and* had patent protection available
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>--thereby, discouraging the maintenance of them as trade secrets.
I dispute this line. I think it's better rendered "held higher
commercial value, leading to efforts to monopolize previously open, basic
research via patents". This is then an argument that those patent have
negative benefits.
>Of course, this isn't saying anything substantively different from what I've
>said in many other posts. By now I'm getting pretty tired of repeating
>myself. If you disagree with this, feel free to post your thoughts, but
>don't count on me to offer a response. I don't have the impression that
>there's anything more I can say that hasn't already been said, *many* times
>over now...
Yes. I think the problem is whether one considers there to be a
significant differences between hardware and software, AND whether this
invalidates the analogy. You want the analogy to be *presumed* valid.
But then your response to any problem will be "we'll fix it, try it and
see". This is completely unconvincing to those of us who see that as
very weak and something that can always be used. But of course, we can't
*prove* that it won't work, just argue that it's extremely unlikely to
do so. And this comes back to the validity of the analogy. If the
analogy is valid, then that a strong argument. If it isn't, then the
problems now are not aberrations, but harbingers. So the argument tends
to run around on circle, because of the different assumptions.
But I suggest people think not only in terms about whether
software is like hardware, but whether they want programming to be
structurally similar to industrial manufacturing (i.e., large capital
dominated).
David Barker-Plummer
TS> From: t...@u.washington.edu (Tim Smith)
TS> Date: 13 Jan 1995 05:07:15 GMT
Michael I Bushnell <m...@geech.gnu.ai.mit.edu> wrote:
>Two people can start up a software company with about $30,000 capital
>and produce major profit, if they are talented programmers. Their new
>system might easily infringe hundreds of patents; they would have to
>search patent databases for thousands of possibly patented algorithms.
>Each patent search costs between $100 and $1000.
TS> Can you give examples of the kinds of programs where this might
TS> happen? The programmer would have to search for thousands of
TS> algorithms only if their program contained thousands of new
TS> algorithms. What class of programs contains so many new
TS> algorithms?
If you knew in advance that the algorithms were indeed new you
wouldn't need to search. the problem is that you need to search to
verify that you are not infringing existing patents, and you need to
search for each algorithm that you use (unless you know that it is
already subject to patent.)
-- Dave
--
Yeats on USEnet:
Things fall apart; the centre cannot hold;
Mere anarchy is loosed upon the world,
The blood-dimmed tide is loosed and everywhere
the ceremony of innocence is drowned;
The best lack all conviction, while the worst
are full of passionate intensity.
J. S. Greenfield
> One point that deserves more emphasis is that algorithm
>patenting is a back-door to format patenting. That's what we've seen in
>GIF. All you do is to come up with a not obvious "process", (it doesn't
>have to be *good*, it just has to pass the standard), then define
>your format to be the data passed through that process. Bingo, anyone
>who wants to read the files has to do the "process", and so must license
>the patent. Reverse-engineering is no defense, because the "process"
>itself is what's protected.
By my understanding, such a use of a patent would violate existing anti-
trust laws, and be grounds for dismissal of the patent.
Arijan Siska
|> The case of patents is the only one where the defendant starts out at a
|> serious legal disadvantage-- the presumption that the claims are valid.
Why is that?
Isn't the one that sues you supposed to prove you did something, and not you proving you didn't?
Arijan