3
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

4
$\begingroup$

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.

The problem DIV is basically equivalent to the integer factoring problem. It is an open question whether there exists any polynomial-time algorithm for it, but many believe that there probably is no polynomial time algorithm for it.

$\endgroup$
8
  • $\begingroup$ What exactly does it mean to be polynomial in the length of the input? Are you saying that because the input n is log(a) + log(b) that our algorithm is exponentially larger because for every n we input, we do 2^n divisions? For example, if i input <1,000,001, 1,000,000>, n would be 20 + 20, and we end up doing 2^20 steps in the worst case scenario? $\endgroup$
    – John_Titor
    Apr 26, 2019 at 0:43
  • $\begingroup$ 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. $\endgroup$
    – John_Titor
    Apr 26, 2019 at 1:47
  • $\begingroup$ @John_Titor, we'd prefer that you use the 'Ask Question' button to ask follow-up questions. I suggest checking the definition of Co-NP before you ask. $\endgroup$
    – D.W.
    Apr 26, 2019 at 5:13
  • 1
    $\begingroup$ @John_Titor, sorry that it wasn't helpful! For what it's worth, I wasn't trying to be condescending; I had a limited amount of time to help, and I can't tell how much you already do and don't know, so I tried to do what I could within the time available to me. Sorry for leaving the impression that I was talking down to you. $\endgroup$
    – D.W.
    Apr 27, 2019 at 16:44

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