クラスNC
ナビゲーションに移動
検索に移動
【くらすえぬしい (class NC)】
並列計算により解答を効率よく求めることができる問題のクラスの1つ. ある問題がクラスNCに属するときには, 入力サイズ構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\,} の多項式個のプロセッサを使えば, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \log n\,} の多項式時間でその問題の解を求めることができる. 多項式時間アルゴリズムが存在する問題であっても, 本質的に並列化できないものと, できるものとがある. 並列化することによって効率よく解くことができる問題のクラスがNCである.