# How to prove that one problem belongs to class P?

Is there any formal method to prove that one problem belongs to Complexity Class $$\mathbb{P}$$?

For example, how can we prove that the problem of finding $$n^k$$ belongs to Class $$\mathbb{P}$$? We can use the fact that each multiplication can be done in unit time.

If you present an algorithm that can solve this problem with $$\mathcal{O} (\log n)$$ time, can it be a proof?

• It's enough to describe an algorithm that solves any given size-$n$ instance of the problem in $O(n^a)$ time for some constant $a$ independent of $n$. It's important to be clear about the machine model (which says what operations are possible and what time they are considered to take, and whether the size $n$ refers to bits or some larger unit) and what information is part of input to the problem (in your example, $k$ could be considered either part of the input, or a fixed part of the problem). Apr 15, 2021 at 12:11
• $\log n=O(n)$ and $n$ is indeed a polynomial.
– user16034
May 11, 2022 at 9:24

Yes. In fact, any algorithm that runs in polynomial time counts. For examle, even an $$O(n^8)$$ would suffice! Therefore, there is no real need to optimize your algorithms to such extremes.