# Why isn't DIV necessarily in P? [duplicate]

In my formal languages class, we discussed DIV, defined as following:

$$\mathrm{DIV} = \{\langle a,b\rangle : \text{a, b \in N and a has a divisor d for some 1 < d \leq b }\}$$

($$\langle\cdot\rangle$$ means encoded, let's say as binary)

We were told that it isn't known whether DIV is in P and were tasked to prove it was in NP. I naively and mistakenly assumed that DIV was in P because of the following algorithm:

   On input <a,b>
For all 1<d<=b
check if d divides a.
If so, accept.
reject.


I thought that this algorithm would run in polynomial time because we do $$b$$ many divisions at worst. Division is polynomial time, therefore, $$b$$ many divisions is also polynomial time. (also note, $$b < a$$, or DIV is trivially true, where $$d = a$$).

However, i was told that this algorithm is not polynomial time with respect to the input. I don't really understand this part. Something along the lines of since $$a$$ and $$b$$ are encoded in binary, the input is of order $$O(\log n)$$. And that means our b many divisions is actually $$O(b) \cdot O(\text{divisions})$$, and that $$O(b)$$ is $$O(2^{\log b})$$. However, isn't $$2^{\text{log base 2 of b}}$$ the same as $$b$$? How is that not polynomial time?

When we say that an algorithm runs in polynomial time, we mean polynomial in the length of the input to the algorithm, i.e., the number of bits needed to represent the input. Suppose both $$a$$ and $$b$$ are at most $$n$$; then the pair $$\langle a,b\rangle$$ takes $$\lg n$$ bits to represent. So, an algorithm whose running time is $$O(n)$$ takes exponential time (exponential in $$\lg n$$). In particular, your algorithm is an exponential time algorithm.
• As a followup that is slightly unrelated, how can i prove DIV is in co-NP? If I use the following algorithm to prove DIV in NP: Given our input <a,b> Non-deterministically choose d, where 1<d<=b Check if d divides a. If not, reject Else, accept.  I seem to cycle back to having to check every possible input, which would become exponential like above. – John_Titor Apr 26 '19 at 1:47