NC (計算複雑性理論)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2017/10/13 14:37 UTC 版)
計算複雑性理論において、NC(Nick's Class)とは多項式個数のプロセッサで構成される並列計算機で,問題サイズの対数について多項式時間で解ける決定問題の複雑性クラスである。換言すれば、NC に属する問題は、O(nk)個の並列プロセッサを使って O((log n)c) の時間で解ける(c と k は定数)。"Nick's Class" という用語はスティーブン・クックの造語で、計算機科学者 Nick Pippenger にちなんでいる。
|
- 1 NC (計算複雑性理論)とは
- 2 NC (計算複雑性理論)の概要
「NC (計算複雑性理論)」の例文・使い方・用例・文例
- NC (計算複雑性理論)のページへのリンク