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

<p>An excerpt from a <a href="http://people.csail.mit.edu/dmoshkov/courses/pcp/dinur_pcp_overview.pdf">Madhu's paper</a>:</p>

<p>... 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 <strong>Joe Kilian</strong>, personal communication) ...</p>

<p>... far beyond my complexity theory skills :-)</p>

CC BY-SA 2.5
2011-03-02T15:53:18.240Z
This is just another formulation that this problem is NP-complete.
Marc Bury
CC BY-SA 2.5
2011-03-02T17:47:23.610Z
@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 ...
Marzio De Biasi
CC BY-SA 2.5
2011-03-03T23:33:44.510Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-01T21:09:40.473Z
2011-03-01T21:09:40.473Z
Marzio De Biasi
<p>This is an informal efficient deterministic reduction idea (and may be incomplete):</p>

<p><a href="https://en.wikipedia.org/wiki/FRACTRAN" rel="nofollow noreferrer">Fractran</a> 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]\}$</p>

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

CC BY-SA 3.0
2017-04-08T18:34:29.067Z
2017-04-08T18:39:51.120Z
2017-04-08T18:39:51.120Z
Mohammad Al-Turkistany
<p>This is not quite an answer, but it's close. The following is a proof that the problem is NP-hard under randomized reductions.</p>

<p>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 </p>

<p>$$\displaystyle \log L \leq \sum_{p_i \in S} \log p_i \leq \log U.$$</p>

<p>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$. </p>

<p>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&#39;_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.</p>

<p>Now, from <a href="http://en.wikipedia.org/wiki/Prime_gap">wikipedia</a> (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. </p>

<p>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.</p>

CC BY-SA 2.5
2011-02-08T00:25:45.180Z
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?
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-08T02:50:51.320Z
We don't need integers whose logarithms are close to the numbers in an instance of the subset sum problem, we only need integers whose logarithms are approximately proportional to the integers; the constant of proportionality can be chosen so the logarithms are actually much smaller than the integers givn in the instance.. I've edited my answer to try to explain this more clearly.
Peter Shor 
CC BY-SA 2.5
2011-02-08T03:24:27.577Z
@Peter: The assumption in number theory is called the [Cramér's conjecture](http://en.wikipedia.org/wiki/Cram%C3%A9r'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](http://en.wikipedia.org/wiki/Prime_gap) also for reference.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-08T03:32:42.700Z
(cont.) But [prime number theorem](http://en.wikipedia.org/wiki/Prime_number_theorem) already gave us an average $O(\log n)$ prime gap. Is that enough under the high probability requirement? No?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-08T04:31:34.163Z
Cramér's conjecture is more powerful than I need, but the prime number theorem isn't quite enough. For this result, you would need that if you pick a number at random, with high probability you are in a gap of size $O(\log^c n)$ for some constant $c$. The prime number theorem doesn't imply that.
Peter Shor 
CC BY-SA 2.5
2011-02-08T05:33:49.397Z
@Peter: Ah, I see where the problem is. Thanks for the comment!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-08T09:18:37.683Z
I'm thinking of a reduction from the Subset Product problem which is $NP$-complete.
Given a set $S$ of integer numbers and integer $k$, Is there a subset $T \subset S$ such that product of all elements is $T$ equals $k$. ($k= \prod_{a_i \in T} a_i$).

Let $N= \prod_{a_i \in S} a_i$. Now, $S$ has a subset $T$ such that $k= \prod_{a_i \in T} a_i$ if and only if $[k|N]$. What is the flaw?
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-08T13:37:48.110Z
@turkistany: This would work if the elements of $T$ were prime. However, if the elements of $T$ are prime, the problem is reducible to factoring.
Peter Shor 
CC BY-SA 2.5
2011-02-08T16:28:30.223Z
Actually, I think that by using more precision in the $p_i$, you can get by with the following number theory assertion: There is a constant $\alpha < 1$ such that with high probability ($1-1/\log^{c_1} T$), for a random integer $T$, there are $T^\alpha/\log^{c_2} T$ primes between $T$ and $T + T^\alpha$, for some constants $c_1$ and $c_2$. This has a chance of being proven already.
Peter Shor 
CC BY-SA 2.5
2011-02-08T17:56:49.877Z
@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](http://en.wikipedia.org/wiki/Prime_gap) is the work by [Baker, Harman and Pintz](http://plms.oxfordjournals.org/content/83/3/532), with $\alpha = 0.525$, $c_1 = \infty$ (since it holds for probability 1) and $c_2 = 1$.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-08T18:03:55.033Z
I had overlooked the “proportional to” part.  Thanks!
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-01T21:43:47.757Z
Hsien-Chih: Thanks. I've now edited my answer to use your comment and eliminate any unproven number theory assumptions.
Peter Shor 
CC BY-SA 2.5
2011-03-05T01:33:15.197Z
@Peter Shor: According to this article http://rjlipton.wordpress.com/2009/06/09/computing-very-large-sums/ your answer gives the correct reduction (but there isn't any hint if they use also randomized reductions).
Marc Bury
CC BY-SA 3.0
2012-09-27T04:18:28.333Z
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)] ).
Boaz Barak
CC BY-SA 3.0
2012-09-27T04:47:42.427Z
BTW this is probably just nonsense due to the late hour, but perhaps a way to make the reduction deterministic is if (1) for some magical reason it is actually known that there is an almost prime in the interval [x,x+polylog(x)], (2) the subset sum problem is still NP hard if you consider solutions that rather than either taking or not taking each element, can take, say, an integer multiple of 1/10th of the element.
Boaz Barak
CC BY-SA 3.0
2014-12-31T03:04:04.470Z
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.
Timothy Chow
CC BY-SA 3.0
2015-01-01T05:00:37.307Z
@TimothyChow Boaz says two conditions have to be satisfied. Only one of which is number theoretic and the other condition is vaguely written as "the subset sum problem is still NP hard if you consider solutions that rather than either taking or not taking each element, can take, say, an integer multiple of 1/10th of the element".
Turbo
CC BY-SA 3.0
2015-01-02T15:49:57.273Z
@Turbo : Boaz gives two conditions in his second comment, but his first comment states only one condition, which is number-theoretic.  As for your other question, the point of my comment was that Joe Kilian does not know anything beyond what has already been posted here.
Timothy Chow
CC BY-SA 3.0
2017-05-20T09:26:42.083Z
@RickyDemer is counting version of this problem #P complete assuming Cramer's conjecture?
Turbo
CC BY-SA 3.0
2017-05-21T22:53:48.463Z
@Ricky so the difficulty is because of carries? I do not follow your reduction that this problem is #P complete under Cramer's conjecture (also there are no primes involved in your reduction which maybe strange).
Turbo
CC BY-SA 3.0
2017-05-22T05:42:59.763Z
@RickyDemer 'The primes are for the subset-sum to factorization-variant reduction, as described in Peter Shor's answer'. Do you provide a different reduction from #3SAT to #FACTORIZATION-VARIANT?
Turbo
CC BY-SA 3.0
2017-05-22T07:02:48.580Z
@RickyDemer ok that makes sense. BTW what is strongly parsimonious? Is it in https://cs.stackexchange.com/questions/9744/definition-of-strongly-parsimonious-reduction?
Turbo
CC BY-SA 3.0
2017-08-21T21:33:56.493Z
@RickyDemer Does the problem stay $NP$-hard under zero-error randomized reductions even if $N$ has all primes factors distinct with multiplicity $1$ and equal bit length?
Turbo
CC BY-SA 3.0
2017-08-24T07:26:56.253Z
@RickyDemer would you know the answer?
Turbo
CC BY-SA 4.0
2020-08-18T11:19:13.340Z
@PeterShor It seems that if this problem is in $P$ or in $BPP$ then $NP$ is in $P/poly$. Is this true?
VS.
CC BY-SA 4.0
2020-08-18T12:46:32.583Z
@VS. Since [BPP ⊆ P/poly](https://en.wikipedia.org/wiki/P/poly#Bounded-error_probabilistic_polynomial_is_contained_in_P/poly), this is true.
Peter Shor 
CC BY-SA 4.0
2020-08-18T13:38:55.447Z
@PeterShor Sorry are you suggesting if this problem is in bpp then np is in bpp? I am aware of Adleman's result. I just noticed this problem does not have deterministic reduction.
VS.
CC BY-SA 4.0
2020-08-18T14:31:36.967Z
@VS. BPP is a randomized class. You don't need a deterministic reduction. If an NP-complete problem can be reduced to a BPP problem via a randomized reduction, then NP ⊆ BPP, and since BPP ⊆ P/poly, we also get that  NP ⊆ P/poly.
Peter Shor 
CC BY-SA 4.0
2020-08-24T09:44:45.960Z
@PeterShor Sorry I think (from user6973's comment and) your comment that this also proves $NP\subseteq ZPP$ if this problem is in $P$ since this problem in $P$ implies we have $ZPP$ reduced an $NP$ complete problem to a $P$ problem and that $NP=coNP$ since $ZPP$ is closed under complement. Correct?
VS.
CC BY-SA 4.0
2020-08-24T11:02:51.783Z
@VS. That's correct.
Peter Shor 
CC BY-SA 2.5
2011-02-07T23:51:06.907Z
2011-03-01T21:36:52.267Z
2011-03-01T21:36:52.267Z
Peter Shor 
<p><a href="http://www.cs.princeton.edu/theory/complexity/">Arora and Barak</a>'s book presents factoring as the following problem:</p>

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

<p>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?</p>

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

CC BY-SA 3.0
2013-05-24T09:18:28.090Z
@MohammadAl-Turkistany: I think that SUBSET PRODUCT is not strongly NP-complete, see the [final EDIT of this question on cstheory](http://cstheory.stackexchange.com/questions/16902/subset-sum-vs-subset-product-strong-vs-weak-np-hardness)
Marzio De Biasi
CC BY-SA 3.0
2015-08-02T00:58:43.193Z
@MohammadAl-Turkistany A new question was posted here http://mathoverflow.net/questions/212816/are-there-effective-small-intervals-in-which-primes-are-dense. Does this improve Shor's answer?
Turbo
CC BY-SA 3.0
2015-08-02T01:02:23.567Z
@Turbo I don't know. It is better to ask Shor.
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-05-01T11:09:02.527Z
@MohammadAl-Turkistany Is there an NP complete variant of Discrete logarithm problem?
Turbo
CC BY-SA 3.0
2017-05-01T11:18:53.353Z
@Turbo I am not aware of any such problem.
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-07T13:49:37.237Z
@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).
Michaël Cadilhac
CC BY-SA 2.5
2011-02-07T13:52:53.610Z
@Michaël, Sorry, reverted back to the original style. I got excited by your question :)
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-07T14:35:27.053Z
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).
Sadeq Dousti
CC BY-SA 2.5
2011-02-07T14:57:20.180Z
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). :(
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-07T21:06:58.683Z
@Michael I actually like rendering classes as $\mathsf{NP}$ rather than NP. No ?
Suresh Venkat
CC BY-SA 2.5
2011-02-07T22:35:15.190Z
@Suresh: Yes, this is something I can root for, even though my typography professor always sheds a tear when multiple fonts (and serifs) appear in a single sentence :-)  But sans-serif for classes is neat.
Michaël Cadilhac
CC BY-SA 2.5
2011-02-08T09:29:21.673Z
I'm thinking of a reduction from the Subset Product problem which is $NP$-complete.
Given a set $S$ of integer numbers and integer $k$, Is there a subset $T \subset S$ such that product of all elements is $T$ equals $k$. ($k= \prod_{a_i \in T} a_i$).

Let $N= \prod_{a_i \in S} a_i$. Now, $S$ has a subset $T$ such that $k= \prod_{a_i \in T} a_i$ if and only if $[k|N]$. What is the flaw?
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-08T11:03:55.170Z
So the reduction maps $(S, k) \rightarrow (k,k, \prod_{a_i \in S} a_i)$
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-08T12:45:45.520Z
Aren't you asuming that the $a_i$'s are prime numbers?  But this is the angle on which I attacked the problem at first.
Michaël Cadilhac
CC BY-SA 2.5
2011-02-08T12:50:11.660Z
@Michaël, No. The definition of Subset Product problem does not require $a_i$'s to be prime numbers.
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-08T12:57:45.860Z
Also, Subset Product problem is strongly $NP$-complete.
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-08T13:12:48.783Z
What I meant is that if $S = \{4\}$ and $k = 2$, you'd output True, isn't it?  (Or $S = \{2,3,5,7,11,26\}$ and $k = 13$ if you want to cipher the example.)  This is why we tried to translate this problem using exponents (Subset Exp?), with no real luck.
Michaël Cadilhac
CC BY-SA 2.5
2011-02-08T13:20:02.547Z
In general, $k$ may not be prime. So, $a_i$'s and $k$ are not necessarily prime numbers.
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-08T13:24:29.420Z
Sorry, I probably didn't make myself clear.  I'm saying that using your reduction, $S=\{4\}$ and $k = 2$ is a counter-example (as Subset Product answers "false" and the FactoringNonPrime would answer "true").  Am I misunderstanding something?
Michaël Cadilhac
CC BY-SA 2.5
2011-02-08T13:35:44.550Z
$S=\{ 4 \}$ and $k=2$ is Yes example for Subset Product problem based on its definition. The certificate for Factoring problem does not need to be non-prime. The only requirement in both problems is that $a_i$'s, $k$, and $p$ are **integers**.
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-08T13:39:20.660Z
Sorry to insist there, but the only subsets of $S = \{4\}$ being $S$ and $\emptyset$, the only products of all elements in them are $4$ and $0$, none of which is $2$.
Michaël Cadilhac
CC BY-SA 2.5
2011-02-08T13:50:51.913Z
Thanks. I got it. The reduction does not work. I'm gonna try to salvage it. :)
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-03-01T21:41:10.453Z
Is it clear that Alon and Kilian proved this problem was NP-hard, and not just NP-hard under randomized reductions?
Peter Shor 
CC BY-SA 2.5
2011-03-02T14:07:37.067Z
@Peter, It is not clear. the referenced textbook states that it is NP-complete (most probably using deterministic reduction).
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-03-03T17:30:14.600Z
I would say so too, as (at least at this point in the book) only deterministic reduction is presented.  But I very much like the last formulation of your solution, Peter; so I'll just wait a little bit more to see if someone can come up with a deterministic version, and otherwise, I'll gladly accept your answer.
Michaël Cadilhac
<cc.complexity-theory><np-hardness><factoring>
An NP-complete variant of factoring.
Michaël Cadilhac
# An NP-complete variant of factoring.

(Asked by: username_0 on 2011-02-07)

[Arora and Barak](http://www.cs.princeton.edu/theory/complexity/)'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.

**Tags:** cc.complexity-theory, np-hardness, factoring
> **Comments:**
> **username_0**: @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).  
> **username_3**: @Michaël, Sorry, reverted back to the original style. I got excited by your question :)  
> **username_4**: 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).  
> **username_5**: 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). :(  
> **username_6**: @Michael I actually like rendering classes as $\mathsf{NP}$ rather than NP. No ?  
> **username_0**: @Suresh: Yes, this is something I can root for, even though my typography professor always sheds a tear when multiple fonts (and serifs) appear in a single sentence :-)  But sans-serif for classes is neat.  
> **username_3**: I'm thinking of a reduction from the Subset Product problem which is $NP$-complete. Given a set $S$ of integer numbers and integer $k$, Is there a subset $T \subset S$ such that product of all elements is $T$ equals $k$. ($k= \prod_{a_i \in T} a_i$).  Let $N= \prod_{a_i \in S} a_i$. Now, $S$ has a subset $T$ such that $k= \prod_{a_i \in T} a_i$ if and only if $[k|N]$. What is the flaw?  
> **username_3**: So the reduction maps $(S, k) \rightarrow (k,k, \prod_{a_i \in S} a_i)$  
> **username_0**: Aren't you asuming that the $a_i$'s are prime numbers?  But this is the angle on which I attacked the problem at first.  
> **username_3**: @Michaël, No. The definition of Subset Product problem does not require $a_i$'s to be prime numbers.  
> **username_3**: Also, Subset Product problem is strongly $NP$-complete.  
> **username_0**: What I meant is that if $S = \{4\}$ and $k = 2$, you'd output True, isn't it?  (Or $S = \{2,3,5,7,11,26\}$ and $k = 13$ if you want to cipher the example.)  This is why we tried to translate this problem using exponents (Subset Exp?), with no real luck.  
> **username_3**: In general, $k$ may not be prime. So, $a_i$'s and $k$ are not necessarily prime numbers.  
> **username_0**: Sorry, I probably didn't make myself clear.  I'm saying that using your reduction, $S=\{4\}$ and $k = 2$ is a counter-example (as Subset Product answers "false" and the FactoringNonPrime would answer "true").  Am I misunderstanding something?  
> **username_3**: $S=\{ 4 \}$ and $k=2$ is Yes example for Subset Product problem based on its definition. The certificate for Factoring problem does not need to be non-prime. The only requirement in both problems is that $a_i$'s, $k$, and $p$ are **integers**.  
> **username_0**: Sorry to insist there, but the only subsets of $S = \{4\}$ being $S$ and $\emptyset$, the only products of all elements in them are $4$ and $0$, none of which is $2$.  
> **username_3**: Thanks. I got it. The reduction does not work. I'm gonna try to salvage it. :)  
> **username_7**: Is it clear that Alon and Kilian proved this problem was NP-hard, and not just NP-hard under randomized reductions?  
> **username_3**: @Peter, It is not clear. the referenced textbook states that it is NP-complete (most probably using deterministic reduction).  
> **username_0**: I would say so too, as (at least at this point in the book) only deterministic reduction is presented.  But I very much like the last formulation of your solution, Peter; so I'll just wait a little bit more to see if someone can come up with a deterministic version, and otherwise, I'll gladly accept your answer.  
> **username_1**: @MohammadAl-Turkistany: I think that SUBSET PRODUCT is not strongly NP-complete, see the [final EDIT of this question on cstheory](http://cstheory.stackexchange.com/questions/16902/subset-sum-vs-subset-product-strong-vs-weak-np-hardness)  
> **username_2**: @MohammadAl-Turkistany A new question was posted here http://mathoverflow.net/questions/212816/are-there-effective-small-intervals-in-which-primes-are-dense. Does this improve Shor's answer?  
> **username_3**: @Turbo I don't know. It is better to ask Shor.  
> **username_2**: @MohammadAl-Turkistany Is there an NP complete variant of Discrete logarithm problem?  
> **username_3**: @Turbo I am not aware of any such problem.  

---

## 3 answers

### Answer by username_7 on 2011-02-07. Score: 39 | Accepted answer

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](http://en.wikipedia.org/wiki/Prime_gap) (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.

> **Comments:**
> **username_5**: 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?  
> **username_7**: We don't need integers whose logarithms are close to the numbers in an instance of the subset sum problem, we only need integers whose logarithms are approximately proportional to the integers; the constant of proportionality can be chosen so the logarithms are actually much smaller than the integers givn in the instance.. I've edited my answer to try to explain this more clearly.  
> **username_9**: @Peter: The assumption in number theory is called the [Cramér's conjecture](http://en.wikipedia.org/wiki/Cram%C3%A9r'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](http://en.wikipedia.org/wiki/Prime_gap) also for reference.  
> **username_9**: (cont.) But [prime number theorem](http://en.wikipedia.org/wiki/Prime_number_theorem) already gave us an average $O(\log n)$ prime gap. Is that enough under the high probability requirement? No?  
> **username_7**: Cramér's conjecture is more powerful than I need, but the prime number theorem isn't quite enough. For this result, you would need that if you pick a number at random, with high probability you are in a gap of size $O(\log^c n)$ for some constant $c$. The prime number theorem doesn't imply that.  
> **username_9**: @Peter: Ah, I see where the problem is. Thanks for the comment!  
> **username_3**: I'm thinking of a reduction from the Subset Product problem which is $NP$-complete. Given a set $S$ of integer numbers and integer $k$, Is there a subset $T \subset S$ such that product of all elements is $T$ equals $k$. ($k= \prod_{a_i \in T} a_i$).  Let $N= \prod_{a_i \in S} a_i$. Now, $S$ has a subset $T$ such that $k= \prod_{a_i \in T} a_i$ if and only if $[k|N]$. What is the flaw?  
> **username_7**: @turkistany: This would work if the elements of $T$ were prime. However, if the elements of $T$ are prime, the problem is reducible to factoring.  
> **username_7**: Actually, I think that by using more precision in the $p_i$, you can get by with the following number theory assertion: There is a constant $\alpha < 1$ such that with high probability ($1-1/\log^{c_1} T$), for a random integer $T$, there are $T^\alpha/\log^{c_2} T$ primes between $T$ and $T + T^\alpha$, for some constants $c_1$ and $c_2$. This has a chance of being proven already.  
> **username_9**: @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](http://en.wikipedia.org/wiki/Prime_gap) is the work by [Baker, Harman and Pintz](http://plms.oxfordjournals.org/content/83/3/532), with $\alpha = 0.525$, $c_1 = \infty$ (since it holds for probability 1) and $c_2 = 1$.  
> **username_5**: I had overlooked the “proportional to” part.  Thanks!  
> **username_7**: Hsien-Chih: Thanks. I've now edited my answer to use your comment and eliminate any unproven number theory assumptions.  
> **username_8**: @Peter Shor: According to this article http://rjlipton.wordpress.com/2009/06/09/computing-very-large-sums/ your answer gives the correct reduction (but there isn't any hint if they use also randomized reductions).  
> **username_10**: 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)] ).  
> **username_10**: BTW this is probably just nonsense due to the late hour, but perhaps a way to make the reduction deterministic is if (1) for some magical reason it is actually known that there is an almost prime in the interval [x,x+polylog(x)], (2) the subset sum problem is still NP hard if you consider solutions that rather than either taking or not taking each element, can take, say, an integer multiple of 1/10th of the element.  
> **username_11**: 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.  
> **username_2**: @TimothyChow Boaz says two conditions have to be satisfied. Only one of which is number theoretic and the other condition is vaguely written as "the subset sum problem is still NP hard if you consider solutions that rather than either taking or not taking each element, can take, say, an integer multiple of 1/10th of the element".  
> **username_11**: @Turbo : Boaz gives two conditions in his second comment, but his first comment states only one condition, which is number-theoretic.  As for your other question, the point of my comment was that Joe Kilian does not know anything beyond what has already been posted here.  
> **username_2**: @RickyDemer is counting version of this problem #P complete assuming Cramer's conjecture?  
> **username_2**: @Ricky so the difficulty is because of carries? I do not follow your reduction that this problem is #P complete under Cramer's conjecture (also there are no primes involved in your reduction which maybe strange).  
> **username_2**: @RickyDemer 'The primes are for the subset-sum to factorization-variant reduction, as described in Peter Shor's answer'. Do you provide a different reduction from #3SAT to #FACTORIZATION-VARIANT?  
> **username_2**: @RickyDemer ok that makes sense. BTW what is strongly parsimonious? Is it in https://cs.stackexchange.com/questions/9744/definition-of-strongly-parsimonious-reduction?  
> **username_2**: @RickyDemer Does the problem stay $NP$-hard under zero-error randomized reductions even if $N$ has all primes factors distinct with multiplicity $1$ and equal bit length?  
> **username_2**: @RickyDemer would you know the answer?  
> **username_12**: @PeterShor It seems that if this problem is in $P$ or in $BPP$ then $NP$ is in $P/poly$. Is this true?  
> **username_7**: @VS. Since [BPP ⊆ P/poly](https://en.wikipedia.org/wiki/P/poly#Bounded-error_probabilistic_polynomial_is_contained_in_P/poly), this is true.  
> **username_12**: @PeterShor Sorry are you suggesting if this problem is in bpp then np is in bpp? I am aware of Adleman's result. I just noticed this problem does not have deterministic reduction.  
> **username_7**: @VS. BPP is a randomized class. You don't need a deterministic reduction. If an NP-complete problem can be reduced to a BPP problem via a randomized reduction, then NP ⊆ BPP, and since BPP ⊆ P/poly, we also get that  NP ⊆ P/poly.  
> **username_12**: @PeterShor Sorry I think (from user6973's comment and) your comment that this also proves $NP\subseteq ZPP$ if this problem is in $P$ since this problem in $P$ implies we have $ZPP$ reduced an $NP$ complete problem to a $P$ problem and that $NP=coNP$ since $ZPP$ is closed under complement. Correct?  
> **username_7**: @VS. That's correct.  

---

### Answer by username_1 on 2011-03-01. Score: 7

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](http://people.csail.mit.edu/dmoshkov/courses/pcp/dinur_pcp_overview.pdf):

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

> **Comments:**
> **username_8**: This is just another formulation that this problem is NP-complete.  
> **username_1**: @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 ...  
> **username_5**: 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.  

---

### Answer by username_3 on 2017-04-08. Score: 1

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

[Fractran](https://en.wikipedia.org/wiki/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$ ).


---

