コブハム・エドモンズのテーゼ
コブハム・エドモンズのテーゼ(Cobham’s Thesis)は、計算複雑性理論において重要な結果となっています。このテーゼは、計算の時間と空間の複雑性を分析する上で、計算資源の限定的な性質に注目することが重要であると主張しています。 具体的には、コブハム・エドモンズのテーゼは、計算に必要な資源の種類が、計算時間と計算空間に影響を与えることを示しています。このテーゼによれば、計算資源が制限されている場合、例えば計算時間が制限されている場合、問題の解決に必要な計算資源の量は、問題の入力サイズに対して多項式的な増加を示すことができます。 このテーゼは、計算複雑性理論における重要な結果であり、NP完全性の証明や、多くの計算問題の解法の設計に役立っています。 具体的には、コブハム・エドモンズのテーゼは、計算問題の解法が、入力サイズに対してどのように計算資源(主に計算時間) (さらに…)