カーマーカーのアルゴリズム
カーマーカーはAT&Tに採用されたのち、彼がこのアルゴリズムを発見してからは、彼と雇用者のAT&Tはこの発明が実用上重要なものとなる、ということを信じて疑わなかった。1985年4月になると、AT&Tは、カーマーカーのアルゴリズムを特許として出願し、ソフトウェア特許問題についての従来からの論争に対し火に油を注いだ。ロナルド・リベストをはじめとする多くの数学者がこの事態の進展を不安視し(しかし、皮肉なことにロナルドはRSA暗号アルゴリズムの特許権保持者の一人である)、アルゴリズムはフリーであるべきとの考えに沿って研究を進めるとの意見を彼らの多くが述べていた。実際に特許が既に許可されたとしても、適用可能な先行技術(英語版)が存在するとも考えられていた。フィリップ・ギル (Philip Gill) などをはじめとする数値解析を専攻する数学者たちは、適切な媒介変数を選択することで、カーマーカーのアルゴリズムが対数障壁関数の射影ニュートン障壁法 (projected Newton barrier method) と同値であることを証明した。ギルが提示した手法は1960年代から非線形計画法に広く利用されている。また事実として、1968年に初版が出版されたある著名な書籍には、線形計画問題の解法としてこの手法が明示されていた。しかし、数名が次のように述べている。彼らが主張する手法が「アルゴリズム」としてさえも見なされない限り、ギルの証明に誤りがある。
n {\displaystyle n} を変数の個数、 L {\displaystyle L} をアルゴリズムの入力ビット数としたとき、カーマーカーのアルゴリズムは、桁数のオーダー O ( L ) {\displaystyle O(L)} に対し、操作数 (operations) のオーダー O ( n 3.5 L ) {\displaystyle O(n^{3.5}L)} をもつ。比較として、楕円体法の操作数は O ( n 6 L ) {\displaystyle O(n^{6}L)} のオーダーをもつ。カーマーカーのアルゴリズムの実行時間(runtime、計算量)は、高速フーリエ変換に基づく乗算であるシェーンハーゲ・シュトラッセンのアルゴリズムで使用した場合、以下のオーダーをもつ。
O ( n 3.5 L 2 ⋅ log  L ⋅ log  log  L ) {\displaystyle O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L)}
(記号"O"についてはランダウの記号を参照のこと。)
なぜなら、その手法は内部的なアルゴリズムからは導けない媒介変数を選択する必要があることを示しているが、それは外部の補助に依存、すなわち実質的にはカーマーカーのアルゴリズムから導かれるものだからである。そのうえ、ザルツマン (Saltzman) が引用している、フィアッコ=マコーミック (Fiacco-McCormick)、ギル、その他の人物による全ての先行作業を考慮してみると、カーマーカーが与えた貢献は明快なものとは程遠いと考えられる。この発明は1988年5月、アメリカ合衆国特許第 4,744,026号"Methods and apparatus for efficient resource allocation"(最適資源割当のための方法および装置)として結局許可された。このアルゴリズムは射影変換とアフィン変換の組合せによる線形計画問題の解法であり、米国の特許では双方のアルゴリズムそれぞれに特許が与えられている。日本では後者だけに特許が出願公告(当時)され、その後特許が認められた。
特許第2033073号「最適資源割当方法」
特願昭61-501865
特公昭62-502580
特公平5-61672
しかし、AT&Tにとってこの特許の商用的価値は限られたものになった。彼らはKORBXというシステムを製造した。このシステムは、アライアント製のプロセッサ8つを搭載し、カーマーカーのアルゴリズムを使用するソフトウェアを組み合わせて線形計画問題を解くという専用システムであり、1台890万ドルもの値段が付けられていた。しかし、売れたのは2台だけだった。