Loading article…
計算複雑性理論において、計算複雑性クラス NEは、あるkに対して非決定性チューリングマシンによって時間O ( kn )で解くことができる決定問題の集合である。[1]
NE は、類似のクラスNEXPTIMEとは異なり、多項式時間の 多対一縮約に対して閉じていません。
他のクラスとの関係
NE はNEXPTIMEに含まれています。
参照
参考文献
- ^ 複雑動物園: NE
計算複雑性理論において、計算複雑性クラス NEは、あるkに対して非決定性チューリングマシンによって時間O ( kn )で解くことができる決定問題の集合である。[1]
NE は、類似のクラスNEXPTIMEとは異なり、多項式時間の 多対一縮約に対して閉じていません。
NE はNEXPTIMEに含まれています。