Is there any typical proving method when proving that one problem belongs to class P?

For example, when proving that

The problem of finding n to the kth power is the P problem. (Each multiplication can be done in unit time)

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

  • 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 Apr 15 at 12:11
  • $\begingroup$ @j_random_hacker I see. Thanks for answer! $\endgroup$ – t24akeru Apr 15 at 12:50

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.

  • $\begingroup$ I understood. thank you! $\endgroup$ – t24akeru Apr 15 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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