Что означает временная сложность n^(O (k))?

Question

Недавно я столкнулся с проблемой и прочитал, что ее можно решить за время n^(O (k)) и что это все еще означает, что проблема в NP. Что представляет собой эта сложность? Как это не детерминированная полиномиальная временная сложность?

Answer 1

Из него следует, что его в NP, потому что P является подмножеством NP, а n^(O (k)) является многочленом, когда k постоянна.

Так что, если это можно решить за полиномиальное время, то его в P и P находится в NP, поэтому проблема также в NP.

РЕДАКТИРОВАТЬ: Это при условии, что К является постоянным или «меньше», чем п (при п-> бесконечной)