An NP-complete variant of factoring.

Question

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.

Answer 1

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.

Answer 2

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 :-)

Answer 3

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