Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
I suppose it is prime factor of at most $k$? Please check if my edit is correct. –  A.Schulz Nov 25 '12 at 20:59
    
Yes, prime factor is correct, thanks. –  Guest Nov 25 '12 at 21:02
    
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? –  Raphael Nov 26 '12 at 11:53
add comment

2 Answers 2

up vote 4 down vote accepted

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.

sp(x):
  min = 2
  max = x - 1
  while (max >= 1 + min):
    k = floor ((min + max) / 2)
    if dec(k, x):
      max = k
    else:
      min = k + 1
  if x % (min + 1) == 0:
    return (min + 1)
  else if x % min == 0:
    return min
  else:
    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:

factor(x):
  p = sp(x)
  if (p == 1):
    print x
  else:
    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)$.

share|improve this answer
add comment

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)$.

share|improve this answer
1  
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. –  Vor Nov 26 '12 at 0:46
    
Yes, I forgot to mention the encoding issues, jmad seems to have covered it all in his answer. –  Luke Mathieson Nov 26 '12 at 4:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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