1
$\begingroup$

I have been trying to figure out why this problem is supposedly not in $P$. Eager to learn where my reasoning is wrong!

Problem:

Given a pair of integers ($n$, $m$) in binary, does there exist $2 \leq k \leq m$ such that $k$ divides $n$?

Reasoning:

In order to find a potential $k$ we need to loop over all numbers from 2 to $m$, which takes a linear time. For each number we need to perform the modulo computation, which takes a constant time. Hence, in total we require a linear time to loop over all possible candidates, which is within the poly-time and hence this problem is in $P$.

$\endgroup$
2
  • $\begingroup$ For $m=n$ this is primality testing and it is in P, though. Of course, your brute force algorithm does not solve it in polynomial time. Otherwise I'd think it's an open problem, not proven to not be in P. $\endgroup$
    – rus9384
    Dec 13, 2023 at 11:21
  • $\begingroup$ In this case, note that $m=2^l$ where $l$ is the length of the input in binary. As you can see, $m$ is exponential, so your algorithm takes exponential time in the worst case. $\endgroup$
    – ultrajohn
    Dec 13, 2023 at 11:58

1 Answer 1

3
$\begingroup$

Because $n$ and $m$ are given in binary, the length of the input is $O(\log n + \log m)$. Looping from 2 to $m$ will in this case require time not linear, but exponential in the size of the input.

$\endgroup$

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.