時間の複雑さn ^（O（k））は何を表していますか？

私は最近問題に遭遇し、それが時間n ^（O（k））で決定される可能性があり、これは依然として問題がNPにあることを意味することを読む。この複雑さは何を表していますか？どのように非決定論的な多項式時間の複雑さですか？時間の複雑さn ^（O（k））は何を表していますか？

これは、PがNPのサブセットであるため、そのNP内にあることを意味し、kが定数であるとき、n ^（O（k））は多項式です。

したがって多項式時間で決定できればPであり、PはNPであるので、NPにも問題があります。

EDIT：これは、kがn（定数または（場合N->無限）N

2016-05-01 09:43:05

また、N ^（O（K））がより一般的に書かれているOよりも "小さい" であるという仮定の下にあります^ k）となり、多項式がより明らかになります。 – Timwi

ありがとうございました。しかし、問題がどのようにその複雑さをもたらすのかはまだ分かりませんが（すなわち、n ^（O（k）））。その複雑さは意味的にどういう意味ですか？ – user3821281

答えて