複雑性クラス
複雑性クラス(ふくざつせいくらす、Complexity class)
P、NP、NP完全、P≠NP以外にも計算の大変さ?を分類したものがあった。
計算の複雑さを分類したものを複雑性クラスというらしい。
複雑性クラスの定義は以下。
抽象機械$ M により$ O(f(n)) の計算資源$ R を使って解く事が出来る問題の集合($ n は入力長) 確認用
Q. 複雑性クラス
参考
関連
メモ
https://youtu.be/gX964OBwQfQ?si=VV5XLbDGR1yvX8U3