Optimization factoring:
Input: $N\in \mathbb{N}$
Output: All prime factors of $N$

Decision factoring:
Input: $N, k\in \mathbb{N}$
Output: True iff $N$ has a prime factor of at most $k$

How can I solve the optimization problem in polynomial time if the decision problem is polynomially solvable?

  • $\begingroup$ This question is a bit thin, and smacks like an exercise problem copied here. What have you tried, what are the specific problems you encountered? $\endgroup$
    – Raphael
    Nov 26 '12 at 11:53

You need to get an algorithm polynomial in $n$ where $n = \log N$ is the size of your input, i.e. the binary representation of $N$ (naive factorization algorithms are $O(N^2)$ which is of course exponential).

Given dec(k, x) solving the decision factoring problem, let's write a procedure to find the smallest prime divisor of $x$ using a dichotomy to keep logarithmic the number of steps.

  min = 2
  max = x - 1
  while (max >= 1 + min):
    k = floor ((min + max) / 2)
    if dec(k, x):
      max = k
      min = k + 1
  if x % (min + 1) == 0:
    return (min + 1)
  else if x % min == 0:
    return min
    return 1

The procedure above calls dec $O(\log x)$ times and find the smallest prime number that divides $x$, or 1 if it does not exist. Now we can easily define the following factoring function:

  p = sp(x)
  if (p == 1):
    print x
    print p
    factor(x / p)

Factor is called less than $\log x$ times (since $p ≥ 2$) so the number of calls to dec is bounded by $\log^2 x$ times on values less than $x$. If the complexity of dec is polynomial, let's say bounded by an increasing $P(n)$, then the complexity of factor is still polynomial, bounded by $n^2P(n)$.


You can use the decision version to search for the factors of $N$ by manipulating $k$. Given the input to the optimization version, you can ask if it has a prime factor less than or equal to $2$, $3$, ..., $\sim\sqrt{N}$ . Say you get your first answer at $k_{1}$, then because it didn't say yes before, $k_{1}$ must be a factor of $N$, so we can note this down, and start again from $\frac{N}{k_{1}}$.

Ideally we'd only test the primes up to $\sim\sqrt{N}$, but it doesn't matter if we test the composites as well, as we'll hit their prime factors first, so we'll never get a Yes answer for a composite.

Then for each individual search we're solving at most $\sqrt{N}$ decision problems, and at each step (until we're done) we're reducing $N$ to less than $\frac{N}{2}$, so if we can solve the decision problem in PTIME (say $O(n^{c})$ for some constant $c$), we can do the whole thing in something roughly like $O(n^{c+1/2}\log n)$.

  • 1
    $\begingroup$ The input $N$ is in binary so its size is $\log N$, and if you check $2,3,...\sim\sqrt{N}$ the running time can be exponential (if for example $N$ is prime). I think you should use a binary search on $k$ to get a polynomial bound on the number of queries. $\endgroup$
    – Vor
    Nov 26 '12 at 0:46
  • $\begingroup$ Yes, I forgot to mention the encoding issues, jmad seems to have covered it all in his answer. $\endgroup$ Nov 26 '12 at 4:25

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.