素因数分解問題
素因数分解問題とは、ある正の整数を素数の積の形に分解する計算上の問題です。小さな数であれば容易ですが、巨大な数の場合は最新のスーパーコンピュータでも膨大な計算時間を要するため、現代のセキュリティ基盤である暗号技術に広く応用されています。近年は、量子コンピュータの登場によって高速に解かれる可能性が指摘され、注目を集めています。
計算複雑性理論のAI用語一覧
4件計算複雑性理論に関するAI用語を4件掲載しています。意味や使い方、関連用語を一覧から確認できます。
P問題
P問題とは、多項式時間という現実的な計算時間内で効率的に解を求められる決定性チューリングマシンの判定問題のクラスです。現代のコンピュータサイエンスやAIの計算限界を理解する上で、NP問題との比較やアルゴリズム設計の基礎となる極めて重要な概念です。
NP完全問題
NP完全問題とは、計算複雑性理論における問題のクラスの一つで、「効率的に解くアルゴリズムが見つかっていないが、提示された解が正しいかを検証することは容易な問題」の中で最も難しい一群を指します。AIや巡回セールスマン問題などの組み合わせ最適化問題の計算コストを理解する上で、基礎となる重要な概念です。
非決定性チューリングマシン
非決定性チューリングマシンとは、ある状態と読み取った文字から次の状態が一意に決まらず、複数の可能性を同時に分岐して探索できる仮想的な計算モデルです。計算複雑性理論において、P問題とNP問題の定義や比較を行う際の根幹となる重要な概念です。