計算可能性と複雑性に関するトピック一覧JJapedia 編集部|更新日: 2026年7月26日これは、ウィキペディアのページごとに分類した、計算可能性と複雑性に関するトピックの一覧です。計算可能性理論は、計算理論のうち、原理的に何が計算可能かを扱う部分である。計算複雑性理論は、計算の難しさを定量的に扱い、上限（最悪の場合の計算リソースの使用など、アルゴリズムの複雑さを推定できる）と下限（あるタスクを実行する手順が非常に高速になり得ないことの証明）の両方を用いる。計算ルックアップテーブル数学表九九表三角関数表の作成コンピュータの歴史乗算アルゴリズム農民の増殖2で割る2乗による指数化連鎖反応ショルツ予想プレスバーガー算術計算可能性理論：計算のモデル算術回路アルゴリズム手続き、再帰有限状態オートマトンミーリーマシンミンスキーレジスターマシンムーアマシン状態図状態遷移システム決定性有限オートマトン非決定性有限オートマトン一般化非決定性有限オートマトン通常の言語ポンピング補題マイヒル・ネロードの定理正規表現通常の文法接頭辞文法ツリーオートマトンプッシュダウンオートマトン文脈自由文法ビュヒ・オートマトンチョムスキー階層文脈依存言語、文脈依存文法再帰的に列挙可能な言語レジスターマシンスタックマシンペトリネット郵便機書き換えマルコフアルゴリズム用語の書き換え文字列書き換えシステムLシステムクヌース・ベンディックス補完アルゴリズム星の高さ星の高さの問題一般化された星の高さの問題セルオートマトンルール110セルオートマトンコンウェイのライフゲームラングトンアリ混沌の淵チューリングマシン決定論的チューリングマシン非決定性チューリングマシン交互オートマトン交代チューリングマシンチューリング完全チューリング・タールピットオラクルマシンラムダ計算組み合わせ論理コンビネーターB、C、K、Wシステム並列コンピューティングフリンの分類法量子コンピュータ汎用量子コンピュータチャーチ＝チューリングのテーゼ再帰関数意思決定問題Entscheidungsproblem停止問題正確さ郵便物の通信問題決定可能な言語決定不能な言語グループ向けの文章問題王タイルペンローズタイル定義可能性に関する質問計算可能な数定義可能な数停止確率アルゴリズム情報理論アルゴリズム確率データ圧縮複雑性理論アドバイス（複雑性）償却分析アーサー・マーリンプロトコル最良の場合と最悪の場合働き者のビーバー回路の複雑さ構築可能な関数クック＝レヴィンの定理指数関数的な時間機能の問題線形時間線形加速定理自然な証明多項式時間多項式時間多対一還元多項式時間チューリング還元サビッチの定理空間階層定理スピード優先スピードアップ定理2次以下の時間時間階層定理複雑性クラス指数階層多項式階層名前付き問題派閥問題ハミルトンサイクル問題ハミルトン経路問題整数因数分解ナップサック問題充足可能性問題2-充足可能性ブール充足可能性問題部分和問題3SUM巡回セールスマン問題頂点被覆問題一方向機能セットカバーの問題独立集合問題拡張機能確率的アルゴリズム、ランダム化アルゴリズムラスベガスのアルゴリズム非決定論非決定性チューリングマシン対話型計算対話型証明システム確率的チューリングマシン近似アルゴリズムシミュレーテッドアニーリングアリコロニー最適化アルゴリズムゲーム意味論一般化ゲームマルチエージェントシステムパラメータ化された複雑性プロセス計算円周率計算ハイパーコンピューティング実際の計算計算可能な解析ヴァイラウフ還元可能性関連項目アルゴリズムの一般的なトピック一覧アルゴリズム一覧数学論理学のトピック一覧–より抽象的な基礎事項について カテゴリー：複雑性クラス数学関連リスト計算理論数学と論理学の概要概要非表示のカテゴリ:短い説明付きの記事短い説明はWikidataとは異なります動的リスト関連するトピック関連計算可能性理論は、関連計算関連計算複雑性理論は関連アルゴリズム
