[Computational Complexity] 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?
Posted By Lance to Computational Complexity at 7/23/2009 09:33:00 AM