コブハムの論文

コブハムのテーゼ（コブハム・エドモンズのテーゼとも呼ばれる。アラン・コブハムとジャック・エドモンズにちなんで名付けられた）^{[ 1 ] [ 2 ] [ 3 ]}は、計算問題が何らかの計算装置上で実行可能に計算できるのは、それが多項式時間で計算できる場合、つまり複雑性クラスPに属する場合に限られると主張している。^{[ 4 ]}現代の用語で言えば、複雑性クラスPに属する扱いやすい問題を特定するものである。

正式には、問題が多項式時間で解決できると言うことは、入力としてnビットの問題インスタンスが与えられたときに、ビッグ オー記法を使用して O( n ^c ) の時間で解を生成できるアルゴリズムが存在することを意味します。ここでc は問題に依存しますが、問題の特定のインスタンスには依存しない定数です。

アラン・コブハムの1965年の論文「関数の本質的な計算の難しさ」^{[ 5 ]}は、多項式時間で決定可能な問題からなる複雑性クラスPの概念について最初に言及したものの1つである。コブハムはこの複雑性クラスが、実行可能な計算問題の集合を記述する良い方法であると理論づけた。

ジャック・エドモンズの1965年の論文「道、木、花」^{[ 6 ]}もまた、Pを扱いやすい問題と結びつけたことで知られている。^{[ 7 ]}

コブハムのテーゼは計算複雑性理論の発展における重要なマイルストーンであるが、アルゴリズムの実用性への適用においては限界がある。テーゼは基本的に「P」は「簡単、高速、実用的」を意味し、「Pに含まれない」は「困難、低速、非実用的」を意味すると述べている。しかし、これは必ずしも真実ではない。なぜなら、テーゼは実際の実行時間に影響を与えるいくつかの重要な変数を抽象化しているからである。

• 定数項と低次の項は無視されます。
• これは指数の大きさを無視する。時間階層定理は、Pにおいて任意の大きな指数を必要とする問題が存在することを証明する。
• 入力の一般的なサイズを無視します。

これら3つはすべて関連しており、アルゴリズムの分析に関する一般的な不満ですが、特にコブハムのテーゼに当てはまります。なぜなら、コブハムのテーゼは実用性について明確な主張をしているからです。コブハムのテーゼでは、最良のアルゴリズムがn ²⁰⁰命令を要する問題は実行可能とみなされ、2 ^{0.00001 n}命令を要するアルゴリズムの問​​題は実行不可能とみなされます。前者のアルゴリズムではn  = 2サイズのインスタンスを解くことは決してできませんが 、後者のアルゴリズムではn  =  10 ^{6サイズのインスタンスを容易に解くことができます。実用的な問題が数百万の変数を持つ分野（}オペレーションズリサーチや電子設計自動化など）では、O( n ³ ) アルゴリズムでさえ実用的でないことがよくあります。^{[ 9 ]}

別の考慮事項として、多くの場合、厳密解が見つからない場合は近似解で満足することが多いという点があります。例えば、巡回セールスマン問題は多項式時間で厳密に解くことは不可能であると広く考えられていますが（NP困難）、クリストフィデスアルゴリズムなどの手法を用いれば、多項式時間で良好な解を得ることができます。