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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\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.