Arora and Barak's book presents factoring as the following problem:

$\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$

They add, further in Chapter 2, that removing the fact that $p$ is prime makes this problem NP-complete, although this is not linked to the difficulty of factoring numbers. It looks there can be a reduction from SUBSETSUM, but I got stuck finding it. Any better luck around here?

EDIT March 1st: The bounty is for $NP$-completeness proof using deterministic Karp (or Cook) reduction.

  • 5
    $\begingroup$ @turkistany: FWIW, I consider as bad style to put NP in italic, and as both bad style and bad LaTeX to put it in math mode (as the spacing between letters differ). $\endgroup$ – Michaël Cadilhac Feb 7 '11 at 13:49
  • $\begingroup$ @Michaël, Sorry, reverted back to the original style. I got excited by your question :) $\endgroup$ – Mohammad Al-Turkistany Feb 7 '11 at 13:52
  • 7
    $\begingroup$ A somewhat more complete description: On page 63 of the book, they write: Alon and Kilian (in personal communication) showed that in the definition of the language Factoring in Example 2.3, the condition that the factor p is prime is necessary to capture the factoring problem, since without this condition this language is NP-complete (for reasons having nothing to do with the hardness of factoring integers). $\endgroup$ – M.S. Dousti Feb 7 '11 at 14:35
  • 2
    $\begingroup$ Naturally, I searched for a paper by Alon and Kilian containing “factoring” and “NP-complete.” I found none (I guess that this is also natural in some sense). :( $\endgroup$ – Tsuyoshi Ito Feb 7 '11 at 14:57
  • 5
    $\begingroup$ @Michael I actually like rendering classes as $\mathsf{NP}$ rather than NP. No ? $\endgroup$ – Suresh Venkat Feb 7 '11 at 21:06

This is not quite an answer, but it's close. The following is a proof that the problem is NP-hard under randomized reductions.

There's an obvious relation to subset sum which is: suppose you know the factors of $N$: $p_1$, $p_2$, $\ldots$, $p_k$. Now, you want to find a subset $S$ of $p_1$ $\ldots$ $p_k$ such that

$$\displaystyle \log L \leq \sum_{p_i \in S} \log p_i \leq \log U.$$

The problem with trying to use this idea to show the problem is NP-hard is that if you have a subset-sum problem with numbers $t_1$, $t_2$, $\ldots$, $t_k$, you can't necessarily find primes in polynomial time such that $\log p_i \propto t_i$ (where by $\propto$, I mean approximately proportional to). This is a real problem because, since subset-sum is not strongly NP-complete, you need to find these $\log p_i$ for large integers $t_i$.

Now, suppose we require that all the integers $t_1$ $\ldots$ $t_k$ in a subset sum problem are between $x$ and $x(1+1/k)$, and that the sum is approximately $\frac{1}{2}\sum_i t_i$. The subset sum problem will still be NP-complete, and any solution will be the sum of $k/2$ integers. We can change the problem from integers to reals if we let $t'_i$ be between $t_i$ and $t_i+\frac{1}{10k}$, and instead of requiring the sum to be exactly $s$, we require it to be between $s$ and $s + \frac{1}{10}$. We only need to specify our numbers to around $4 \log k$ more bits of precision to do this. Thus, if we start with numbers with $B$ bits, and we can specify real numbers $\log p_i$ to approximately $B + 4 \log k$ bits of precision, we can carry out our reduction.

Now, from wikipedia (via Hsien-Chih's comment below), the number of primes between $T$ and $T+ T^{5/8}$ is $\theta(T^{5/8}/\log T)$, so if you just choose numbers randomly in that range, and test them for primality, with high probability get a prime in polynomial time.

Now, let's try the reduction. Let's say our $t_i$ are all $B$ bits long. If we take $T_i$ of length $3B$ bits, then we can find a prime $p_i$ near $T_i$ with $9/8B$ bits of precision. Thus, we can choose $T_i$ so that $\log T_i \propto t_i$ with precision $9/8\, B$ bits. This lets us find $p_i \approx T_i$ so that $\log p_i \propto t_i$ with precision $9/8\,B$ bits. If a subset of these primes multiplies to something close to the target value, a solution exists to the original subset sum problems. So we let $N=\Pi_i p_i$, choose $L$ and $U$ appropriately, and we have a randomized reduction from subset sum.

  • 3
    $\begingroup$ I do not understand the reduction. For the subset sum problem to be NP-complete, the number must be given in binary. If we want integers whose logarithms are close to the numbers in an instance of the subset sum problem, we need exponentially many digits. How do you overcome this? $\endgroup$ – Tsuyoshi Ito Feb 8 '11 at 0:25
  • 2
    $\begingroup$ @Peter: The assumption in number theory is called the Cramér's conjecture, which states that $p_{n+1} - p_n = O(\log^2 n)$, where $p_n$ is the n-th prime number. See the article prime gap also for reference. $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 8 '11 at 3:24
  • 2
    $\begingroup$ @Peter: Yes, this version of assumption has been proved for $T$ large enough. The first result of this kind is shown by Hoheisel, and the best result due to wikipedia is the work by Baker, Harman and Pintz, with $\alpha = 0.525$, $c_1 = \infty$ (since it holds for probability 1) and $c_2 = 1$. $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 8 '11 at 17:56
  • 2
    $\begingroup$ Just came across this. I should note that I don't know what the original Kilian-Alon proof was. My only knowledge of the proof is from a communication with Noga who didn't remember the details of the original proof, and the proof he reconstructed was exactly this one. Note that it can also be described as a deterministic reduction under some strong number theoretic assumptions (e.g., that there is a prime in any interval of the form [x,x+polylog(x)] ). $\endgroup$ – Boaz Barak Sep 27 '12 at 4:18
  • 4
    $\begingroup$ I just talked to Joe Kilian. He said that the proof that he and Alon came up with involved zero-error randomized reductions. As far as he is aware, deterministic reduction is still open unless you make some number-theoretic assumption, as Boaz Barak has already said. $\endgroup$ – Timothy Chow Dec 31 '14 at 3:04

I think that it is linked to the PCP theorem (in particular $NP = PCP[O(\log{n}), O(1)]$).

An excerpt from a Madhu's paper:

... The notion that a verifier can perform any polynomial time computation enriches the class of theorems and proofs considerably and starts to offer highly non-trivial methods of proving theorems. (One immediate consequence is that we can assume theorems/proofs/assertions/arguments are binary sequences and we will do so henceforth.) For instance, suppose we have an assertion $A$ (say the Riemann Hypothesis), and say we believe that it has proof which would fit within a 10,000 page article. The computational perspective says that given $A$ and this bound (10,000 pages), one can efficiently compute three positive integers $N, L, U$ with $L \leq U \leq N$ such that $A$ is true if and only if $N$ has a divisor between $L$ and $U$. The integers $N$, $L$, and $U$ will be quite long (maybe writing them would take a million pages), yet they can be produced extremely efficiently (in less than the amount of time it would take a printer to print out all these integers, which is certainly at most a day or two). (This specific example is based on a result due to Joe Kilian, personal communication) ...

... far beyond my complexity theory skills :-)

  • 2
    $\begingroup$ This is just another formulation that this problem is NP-complete. $\endgroup$ – Marc Bury Mar 2 '11 at 15:53
  • $\begingroup$ @Marc ... mmm ... I think that it means: $\{\langle L, U, N \rangle \;|\; (\exists p \in \{L, \ldots, U\})[p | N]\}$ is NP-complete because a polynomial reduction from the NP-complete problem SHORT PROOF exists ... $\endgroup$ – Marzio De Biasi Mar 2 '11 at 17:47
  • 2
    $\begingroup$ The SHORT PROOFS problem in the paper is almost the same as the bounded halting problem. A reduction from the SHORT PROOFS problem would be most likely as messy as the typical proof of the NP-completeness of SAT, and therefore it is unlikely that the proof of the NP-completeness of this factor finding problem by Kilian constructs a reduction from the SHORT PROOFS problem directly. $\endgroup$ – Tsuyoshi Ito Mar 3 '11 at 23:33

This is an informal efficient deterministic reduction idea (and may be incomplete):

Fractran is a Turing-complete programming language. A suitably defined bounded-version of Fractran programs should be reducible to the language $ \{\langle L, U, M \rangle \;|\; (\exists \text{ a positive integer } p \in \{L, \ldots, U\})[p | M]\}$

For instance, a bounded-version could ask whether integer $M$ is produced in the output sequence of a Fractran program within certain number of steps (divisions) (i.e. $M=N_j * F_i$ ).


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.