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