Thursday, July 23, 2009

Patenting P=NP

The book Patent Failure by James Bessen and Michael J. Meurer notes that considerable more money is spent on litigation defense for technology patent infringement than on royalties collected and discusses various issues and potential solutions. 

From Chapter 9 (PDF) on Software Patents
Patent law assumes that once the words are mapped to a specific set of technologies, one can readily determine which technologies are equivalent and which are distinct. However, for software, this assumption is not always true. Computer algorithms may be equivalent, but computer scientists may not know that they are equivalent. In any cases, it has taken years for them to discover that different techniques are equivalent. For example, it has been shown that the “traveling salesman” problem, which is used for routing delivery trucks among other things, is more or less equivalent to the “map coloring” problem and a whole range of other problems. This means that an algorithm for solving the traveling salesman problem is also, if worded broadly enough, an algorithm for doing map coloring. In other cases, computer scientists suspect that algorithms are equivalent, but they are unable to prove the equivalence.
More than suspect, we can actually construct two equivalent algorithms where one cannot prove their equivalence in a given mathematical theory (assuming the consistency of that theory). In other words, it is theoretically impossible to determine whether one has software patent infringement in general. So if you are writing some code, it is impossible to determine whether you are infringing on an early patent. A theoretical justification for "Patent Failure".

What about the other part of this paragraph? Lipton might disagree, but we aren't in any danger of someone having a legitimate efficient algorithm for TSP or Coloring to patent. But suppose that someone managed to have such an algorithm and patented it as solving all NP-complete problems. For 17 years, only that person and his/her licensees could efficiently solve all sorts of problems while the rest of us toil away in exponential time. Which of Russell's worlds does this correspond to, Algorithmica Hell?


  1. I an a Chinese . I agree with you

  2. What then can be really patented? It would be ridiculous to patent particular implementations of algorithms, but in an abstract sense, that's exactly what patent law is about.

    When does a competing implementation differ significantly from another implementation? For source code, it can't be changing a comment here or there; the *structure* of the algorithm has to be different - but something tells me determining this so-called "structure" is not a feasible/achievable task.

  3. I'm guessing that if someone gave a polytime algorithm for an NP-complete problem, so many people would be clamoring for it -- not to mention trying to improve the exponent and constants -- that it would be essentially impossible to curtail its spread by patent law.

  4. A radical reader: IP is nonsense, public will benefit more without it, copying is a natural right.