1
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$ Apr 15, 2021 at 12:11
  • $\begingroup$ $\log n=O(n)$ and $n$ is indeed a polynomial. $\endgroup$
    – user16034
    May 11, 2022 at 9:24

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.